Finding simple fixed length paths in directed graphs

Question

Is there an efficient algorithm to enumerate unique simple fixed-length paths (of size $k$) in directed graphs? What would be its time complexity?

Answer 1

The color coding technique for deciding if a graph contains a $k$-path, presented for example in the book Parameterized Algorithms, can be turned into output-sensitive enumeration algorithm for such paths.

The algorithm works in iterations in which a random coloring of $k$ colors is assigned to the vertices of the graph, and then the paths with distinctly colored vertices are identified by dynamic programming. In each iteration, compute by dynamic programming the function $P(S, u)$ denoting the number of paths that use the subset $S$ of colors and end in the vertex $u$. Then trace the positive values in this dynamic programming backwards to enumerate the paths. In this way the paths identified by this coloring can be enumerated in $O(2^km + Pm)$, where $P$ is the number of such paths and $m$ is the number of edges.

A path of length $k$ is identified with probability at least $e^{-k}$, so by the coupon collector analysis $O(e^k k \log n)$ iterations is enough to identify all (possibly $n^k$) paths with constant probability. A path of length $k$ is identified with probability at most $O(e^{-k} k)$, so the total expected time complexity of the algorithm is $O((2e)^k km \log n + P k^2 m \log n)$, where $P$ is the number of paths of length $k$.