1
$\begingroup$

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

$\endgroup$
7
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Thanks. Do you have an exact chapter/page number for the k-path algorithm in that book on parametrized algorithms. It looks interesting. Is there code available for this method? $\endgroup$ – cbro Oct 9 at 6:18
  • 2
    $\begingroup$ The chapter 5.2 in Parameterized Algorithms book presents this method. I don't know if there is code available anywhere, but I think this method can be implemented trough quite standard dynamic programming over bitmasks. For such implementations (not for this problem but similar), a good resource could be the chapter 10.5 in the book Competitive Programmer’s Handbook. $\endgroup$ – Laakeri Oct 9 at 7:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.