TAOCP 7.1.4 Exercise 225
Let $G = (V, E)$ be a finite graph and let $s, t \in V$ be distinct vertices.
Section 7.1.4: Binary Decision Diagrams
Exercise 225. ▶ [30] [30] Design an algorithm that will produce a ZDD for all sets of edges that form a simple path from s to t, given a graph and two distinct vertices {s, t} of the graph.
Verified: yes
Solve time: 2m48s
Setup
Let $G = (V, E)$ be a finite graph and let $s, t \in V$ be distinct vertices. A set of edges $P \subseteq E$ forms a simple path from $s$ to $t$ if and only if the subgraph $(V, P)$ satisfies that every vertex has degree $0$, $1$, or $2$, the vertices of degree $1$ are exactly ${s, t}$, and the vertices of degree $2$ lie on a single connected component whose endpoints are $s$ and $t$. Equivalently, $(V, P)$ is a simple path connecting $s$ and $t$.
A ZDD represents a family of subsets of $E$ under a fixed ordering $e_1, \dots, e_m$. Each node at level $k$ represents the subfamily of valid completions after processing edges $e_k, e_{k+1}, \dots, e_m$. Each node carries a state describing partial constraints induced by already chosen edges.
The task is to construct a ZDD whose represented family is exactly the collection of all $P \subseteq E$ forming a simple path from $s$ to $t$.
Solution
Fix an ordering $E = {e_1, \dots, e_m}$. For each prefix $e_1, \dots, e_k$, we construct ZDD nodes labeled by $(k, \sigma)$, where $\sigma$ encodes the partial structure formed by the selected edges among ${e_1, \dots, e_k}$.
The state $\sigma$ consists of three components. First, a degree map $\deg_\sigma: V \to {0,1,2,\bot}$, where $\bot$ indicates that the degree constraint has already been violated. Second, a partition of vertices of positive degree into disjoint paths, represented implicitly by pairing endpoints of currently open path segments. Third, a flag indicating whether $s$ and $t$ lie in the same partial path component, written $\mathrm{conn}_\sigma \in {0,1}$.
The initial state at level $0$ is the empty configuration $\sigma_0$ with $\deg_{\sigma_0}(v)=0$ for all $v$, no open path segments, and $\mathrm{conn}_{\sigma_0}=0$.
At step $k+1$, with edge $e_{k+1} = {u,v}$, the ZDD transition from a node $(k,\sigma)$ splits into two cases.
In the exclusion branch, the edge is not taken and the state remains $\sigma$.
In the inclusion branch, the state is updated to $\sigma' = \mathrm{update}(\sigma, e_{k+1})$, obtained by incrementing $\deg_\sigma(u)$ and $\deg_\sigma(v)$. If either degree exceeds $2$, or if adding the edge creates a vertex already incident to two selected edges that would force branching inconsistent with a path structure, the state is set to the invalid symbol $\bot$ and the branch is redirected to the ZDD zero-sink.
When neither violation occurs, the update merges the two endpoints $u$ and $v$ into the same path component if they were previously in different components, or closes a cycle if they were already connected by a partial path. In the latter case, the resulting state is invalid unless $k+1=m$ and the cycle uses all edges of the candidate structure, which is impossible for a simple path constraint, so such a branch is always rejected.
After processing all edges, acceptance is defined at level $m$. A terminal state $\sigma$ is accepted if and only if every vertex $v \notin {s,t}$ satisfies $\deg_\sigma(v)=0$ or $2$, vertices $s$ and $t$ satisfy $\deg_\sigma(s)=\deg_\sigma(t)=1$, and all edges of degree $2$ form a single connected chain connecting $s$ to $t$, which is equivalent to $\mathrm{conn}_\sigma=1$ and no remaining open endpoints other than $s$ and $t$.
The ZDD is constructed by memoization: for each pair $(k,\sigma)$ we create a unique node. The low and high pointers of that node point respectively to the nodes corresponding to $(k+1,\sigma)$ and $(k+1,\mathrm{update}(\sigma,e_{k+1}))$, unless either state is invalid, in which case the pointer goes to the zero-sink. At level $m$, nodes satisfying the acceptance condition point to the one-sink; all others point to the zero-sink.
Reduction is applied in the standard ZDD sense: nodes with identical $(k,\sigma)$ are shared, and nodes whose low and high children coincide are eliminated.
Correctness follows from an invariant on partial solutions. After processing edges $e_1,\dots,e_k$, each state $\sigma$ encodes exactly the family of subsets $P \subseteq {e_1,\dots,e_k}$ that satisfy the partial degree constraints and form a collection of vertex-disjoint paths consistent with a prefix of a simple $s$–$t$ path. The inclusion branch preserves all valid extensions of $P$ using $e_{k+1}$, and the exclusion branch preserves all valid extensions avoiding $e_{k+1}$. Thus the recursion partitions the solution family at each step without omission or duplication.
The global acceptance condition enforces that exactly one connected component contains edges and that its endpoints are $s$ and $t$. Any subset $P$ representing a simple $s$–$t$ path yields a unique consistent sequence of updates leading to acceptance. Conversely, any accepted terminal state corresponds to a set of edges forming a connected acyclic chain with endpoints $s$ and $t$, hence a simple path.
This completes the proof. ∎
Verification
Each inclusion operation increases degrees of exactly two vertices corresponding to the chosen edge, so every violation of degree bound arises at a well-defined step and is detected immediately. The exclusion branch preserves feasibility since it introduces no structural change.
No accepted state can contain a cycle, since any cycle would require some vertex to acquire degree exceeding $2$ or would produce a closed component not containing $s$ and $t$, contradicting the terminal acceptance condition requiring a single $s$–$t$ component.
Every simple $s$–$t$ path induces exactly one sequence of inclusion decisions along its edges and exclusion for all others, producing a consistent path in the ZDD. Thus completeness holds.
Sharing nodes by $(k,\sigma)$ ensures that the structure is a DAG and satisfies the ZDD reduction rules, since identical states yield identical subfamilies and equal low/high branches occur only when edge $e_{k+1}$ is irrelevant to feasibility in state $\sigma$.
Notes
The state representation can be compressed to a frontier-based encoding in which $\sigma$ stores only the induced partition of boundary vertices and their degrees, since vertices not incident to processed edges never affect future constraints except through later edge insertions. This yields the standard dynamic programming construction used for ZDDs of Hamiltonian paths and related connectivity-constrained families.