Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR09-012 | 4th February 2009 00:00

Balanced Hashing, Color Coding and Approximate Counting



Color Coding is an algorithmic technique for deciding efficiently
if a given input graph contains a path of a given length (or
another small subgraph of constant tree-width). Applications of the
method in computational biology motivate the study of similar
algorithms for counting the number of copies of a given subgraph.
While it is unlikely that exact counting of this type can be
performed efficiently, as the problem is $\#W[1]$-complete
even for paths,
approximate counting is possible, and leads to the investigation
of an intriguing variant of families of perfect hash functions. A
family of functions from $[n]$ to $[k]$ is an
$(\epsilon,k)$-balanced family of hash functions, if there exists
a positive $T$ so that for every $K \subset [n]$ of size $|K|=k$,
the number of functions in the family that are one-to-one on $K$
is between $(1-\epsilon)T$ and $(1+\epsilon)T$. The family is
perfectly $k$-balanced if it is $(0,k)$-balanced.

We show that every such perfectly $k$-balanced family is of size
at least $c(k) n^{\lfloor k/2 \rfloor}$, and that for every
$\epsilon>\frac{1}{poly(k)}$ there are explicit constructions of
$(\epsilon,k)$-balanced families of hash functions from $[n]$ to
$[k]$ of size $e^{(1+o(1))k} \log n$. This is tight up to the $o(1)$-term
in the exponent, and supplies deterministic
polynomial time algorithms for approximately counting the number
of paths or cycles of a specified length $k$ (or copies of any
graph $H$ with $k$ vertices and bounded tree-width) in a given
input graph of size $n$, up to relative error $\epsilon$, for all
$k \leq O(\log n)$.

ISSN 1433-8092 | Imprint