Summary: 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 \((\varepsilon ,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 - \varepsilon )T\) and \((1 + \varepsilon )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 \(\varepsilon>\frac{1}{\text{poly}(k)}\) there are explicit constructions of \((\varepsilon ,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 \(\varepsilon \), for all \(k \leq O(\log n)\).
For the entire collection see [Zbl 1178.68005].