Approximate Counting of $k$-Paths in $O^*(2^k)$ Time

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