<p>The color coding technique for deciding if a graph contains a <span class="math-container">$k$</span>-path, presented for example in the book <a href="http://parameterized-algorithms.mimuw.edu.pl/parameterized-algorithms.pdf" rel="noreferrer">Parameterized Algorithms</a>, can be turned into output-sensitive enumeration algorithm for such paths. </p>

<p>The algorithm works in iterations in which a random coloring of <span class="math-container">$k$</span> 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 <span class="math-container">$P(S, u)$</span> denoting the number of paths that use the subset <span class="math-container">$S$</span> of colors and end in the vertex <span class="math-container">$u$</span>. 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 <span class="math-container">$O(2^km + Pm)$</span>, where <span class="math-container">$P$</span> is the number of such paths and <span class="math-container">$m$</span> is the number of edges.</p>

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

CC BY-SA 4.0
2019-10-09T06:18:04.517Z
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?
user43464
CC BY-SA 4.0
2019-10-09T07:24:59.520Z
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](https://cses.fi/book/book.pdf).
Laakeri
CC BY-SA 4.0
2019-10-08T21:39:49.560Z
2019-10-08T21:47:09.183Z
2019-10-08T21:47:09.183Z
Laakeri
<p>Is there an efficient algorithm to enumerate <strong>unique</strong> simple fixed-length paths (of size <span class="math-container">$k$</span>) in directed graphs? What would be its time complexity?</p>

<graph-theory><graph-algorithms>
Finding simple fixed length paths in directed graphs
user43464
# Finding simple fixed length paths in directed graphs

(Asked by: username_0 on 2019-10-08)

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

**Tags:** graph-theory, graph-algorithms

---

## 1 answers

### Answer by username_1 on 2019-10-08. Score: 8

The color coding technique for deciding if a graph contains a $k$-path, presented for example in the book [Parameterized Algorithms](http://parameterized-algorithms.mimuw.edu.pl/parameterized-algorithms.pdf), 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$.

> **Comments:**
> **username_0**: 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?  
> **username_1**: 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](https://cses.fi/book/book.pdf).  

---

