TAOCP 7.2.2.1 Exercise 405
Let $G=(V,E)$ be the given graph, let $v \in V$, and let $L \ge 1$.
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: no
Solve time: 1m04s
Solution
Let $G=(V,E)$ be the given graph, let $v \in V$, and let $L \ge 1$. For each integer $k$ with $1 \le k \le L$, let $E_k$ denote the set of vertices $u$ such that there exists a simple path of length $k$ from $v$ to $u$.
The construction uses a depth-limited backtracking search in which vertices are never repeated along a current path. For each vertex $u$, a Boolean marker $\mathrm{VIS}(u)$ is maintained. The value $\mathrm{VIS}(u)=\text{true}$ means that $u$ already appears in the current partial path. All markers are initially false except $\mathrm{VIS}(v)=\text{true}$.
The search is driven by a recursive procedure $\mathrm{DFS}(u,k)$, where $u$ is the current vertex and $k$ is the remaining permitted number of edges. The procedure is defined for all $0 \le k \le L$.
The initial call is $\mathrm{DFS}(v,L)$.
The procedure $\mathrm{DFS}(u,k)$ acts as follows. If $k=0$, then the current vertex $u$ is an endpoint of a simple path of length $L$, so $u$ is inserted into $E_L$ and the procedure returns. If $k>0$, then for each edge $(u,w) \in E$, the vertex $w$ is considered in turn. If $\mathrm{VIS}(w)=\text{false}$, then $\mathrm{VIS}(w)$ is set to true, the call $\mathrm{DFS}(w,k-1)$ is executed, and afterward $\mathrm{VIS}(w)$ is reset to false. This ensures that each explored path remains simple.
To obtain endpoints for all lengths $1,2,\ldots,L$, the recursion is modified so that termination at depth $k=0$ contributes to the appropriate set. In $\mathrm{DFS}(u,k)$, when $k=0$, the current vertex $u$ is inserted into $E_{L-k}$, which equals $E_L$ in the initial call but shifts correctly in recursive calls if depth is tracked directly. A cleaner formulation avoids this shift by introducing an explicit depth parameter.
Define $\mathrm{DFS}(u,d)$, where $d$ is the current path length from $v$. The initial call is $\mathrm{DFS}(v,0)$. The procedure is:
If $d \le L$, the vertex $u$ is inserted into $E_d$. If $d=L$, the procedure returns. Otherwise, for each $w$ with $(u,w) \in E$, if $\mathrm{VIS}(w)=\text{false}$, then set $\mathrm{VIS}(w)\leftarrow \text{true}$, call $\mathrm{DFS}(w,d+1)$, and then set $\mathrm{VIS}(w)\leftarrow \text{false}$.
This explores exactly all simple paths starting at $v$ whose length does not exceed $L$, since every recursive call increases $d$ by exactly one and forbids revisiting vertices already on the current path.
Correctness follows from two inclusions. If $u \in E_d$, then by construction there exists a sequence $v=x_0,x_1,\ldots,x_d=u$ such that each $(x_{i-1},x_i) \in E$ and all $x_i$ are distinct, since $\mathrm{VIS}$ prevents repetition. Conversely, every simple path $v=x_0,\ldots,x_d$ is generated by the unique sequence of recursive choices that selects $x_{i+1}$ when at $x_i$, since adjacency is exhaustively iterated and no forbidden vertex is available at that step.
Each recursive call corresponds to exactly one extension of a partial simple path by one edge, and each extension is reversed after return by resetting $\mathrm{VIS}(w)$, so the state of the search is identical before and after exploring any branch. This guarantees that all simple paths are explored independently of order.
Therefore, for each $1 \le d \le L$, the set $E_d$ produced by the algorithm equals the set of endpoints of all simple paths of length $d$ starting at $v$.
This completes the proof. ∎