Approximate Counting of $k$-Paths in $O^{\ast }(2^k)$ Time

Abstract

We resolve the conjecture of Koutis and Williams that $k$-paths can be approximately counted in $O^{\ast }(2^k)$ time. For a simple directed graph with $n$ vertices and $m$ arcs, our randomized algorithm returns a $(1\pm \epsilon )$-approximation with failure probability at most $\delta$ in $O^{\ast }(2^k{\epsilon }^{-2}\log (1/\delta ))$ time.