TAOCP 7.2.2.1 Exercise 405
Let the graph be $G=(V,E)$, and let $v\in V$ be the specified starting vertex.
Section 7.2.2.1: Dancing Links
Exercise 405. [21] The preceding exercise needs a subroutine to determine the endpoints of all simple paths of lengths $1, 2, \ldots, L$ from a given vertex $v$ in a given graph. That problem is NP-hard; but sketch an algorithm that works well for small $L$ in small graphs.
Verified: yes
Solve time: 1m34s
Solution
Let the graph be $G=(V,E)$, and let $v\in V$ be the specified starting vertex. The required output is, for each length $k$, $1\le k\le L$, the set of vertices that occur as endpoints of simple paths of length $k$ beginning at $v$.
A direct breadth-first search is insufficient because ordinary breadth-first search allows vertices to be revisited along different levels, whereas a simple path may not contain the same vertex twice. The state of the search must therefore include the set of vertices already used on the current path.
For a current partial path, store the pair $(w,S)$, where $w$ is the present endpoint and $S$ is the set of vertices on the path from $v$ to $w$. Initially the only state is
$$ (v,{v}). $$
Maintain a collection of active states. Whenever a state $(w,S)$ is removed, examine every edge $(w,x)$. If $x\notin S$, the extended path is still simple, so insert
$$ (x,S\cup{x}). $$
Whenever a state with endpoint $w$ has length $k$, record $w$ among the endpoints of paths of length $k$. The length of the path represented by $(w,S)$ is
$$ |S|-1, $$
because the path begins with one vertex and every additional vertex contributes one edge.
A compact version of the procedure is therefore:
$$ \begin{array}{l} \text{Set } A_0\leftarrow{(v,{v})}.\[2mm] \text{For } k\leftarrow 1 \text{ to } L\text{ do:}\ \qquad \text{Set } A_k\leftarrow\varnothing.\ \qquad \text{For each }(w,S)\in A_{k-1}\text{ do:}\ \qquad\qquad \text{For each neighbor }x\text{ of }w\text{ do:}\ \qquad\qquad\qquad \text{if }x\notin S,\text{ append }(x,S\cup{x})\text{ to }A_k.\ \qquad \text{The endpoints of length }k\text{ are the first components of the pairs in }A_k. \end{array} $$
The correctness follows from induction on $k$. For $k=0$, $A_0$ contains exactly the one path of length $0$ from $v$, namely the path consisting only of $v$. Assume that $A_{k-1}$ contains exactly all simple paths of length $k-1$ from $v$, represented by their endpoint and their vertex sets. Every extension generated by the procedure adds a neighbor not already in the vertex set, so every generated state represents a simple path of length $k$. Conversely, every simple path of length $k$ has a final edge from a vertex $w$ to a vertex $x$. Removing that final edge leaves a simple path of length $k-1$ represented in $A_{k-1}$, and the procedure examines the edge $(w,x)$ and reconstructs the full path. Thus $A_k$ contains exactly all simple paths of length $k$ from $v$.
The procedure terminates after $L$ extensions. Its running time is proportional to the number of simple paths of length at most $L$ starting at $v$, multiplied by the maximum degree used to extend a path. This exponential growth is unavoidable in general, because the number of such simple paths can itself be exponential in $L$.
This gives a practical algorithm for small $L$ and small graphs, which is the regime required by the preceding exact-cover formulation.