TAOCP 7.1.4 Exercise 224
Let $D$ be a DAG in which every non-source vertex has in-degree $1$.
Section 7.1.4: Binary Decision Diagrams
Exercise 224. ▶ [20] [20] Suppose we form the ZDD for all source-to-sink paths in a dag, as in Fig. 28, when the dag happens to be a forest; that is, assume that every non-source vertex of the dag has in-degree 1. Show that the corresponding ZDD is essentially the same as the binary tree that represents the forest under the “natural correspondence between forests and binary trees,” Eqs. 2.3.2–(1) through 2.3.2–(3).
Verified: yes
Solve time: 4m15s
Let $D$ be a DAG in which every non-source vertex has in-degree $1$. Each weakly connected component is therefore a rooted directed tree. Every source-to-sink path in $D$ is contained in exactly one such tree, so it suffices to analyze a single rooted tree $T$. Let $v$ be a vertex with outgoing edges $e_1,\dots,e_k$, where $e_i=(v,v_i)$, and let $\mathcal{P}(v)$ denote the set of all directed paths from $v$ to a sink, each path being identified with its set of edges.
The key point is that the ZDD is not built from the multiway choice at $v$ directly. It is built from binary decisions on edge variables. The correct way to connect the two is to refine the multiway choice into a binary decision structure whose reduction reproduces the left-child/right-sibling form.
Fix a variable ordering in which, for every vertex $v$, the edges leaving $v$ appear consecutively, and within each such block we order them as
$$ e_1 < e_2 < \cdots < e_k. $$
This ordering is the standard one implicit in the forest-to-binary-tree correspondence in Knuth’s Eqs. 2.3.2-(1)–(3), since the sibling chain is linear and must be read in order. The correctness of the final structure depends on this local consecutivity, because ZDD reduction preserves structure only under a fixed global ordering.
Now consider how the ZDD represents the constraint that a path starting at $v$ must choose exactly one outgoing edge unless $v$ is a sink. Define
$$ \mathcal{P}i(v) = {{e_i} \cup P : P \in \mathcal{P}(v_i)}, \quad \mathcal{P}(v)=\bigcup{i=1}^k \mathcal{P}_i(v). $$
Instead of treating this as a single $k$-way choice, we express it as a sequence of binary decisions in the ZDD ordering $e_1<\cdots<e_k$. At the variable $e_1$, the ZDD must decide whether $e_1$ is in the path. If the answer is 1, then all other edges leaving $v$ must be excluded (since the structure is a path), and the remainder of the path is exactly $\mathcal{P}(v_1)$. Hence the 1-child of the node labeled $e_1$ at state $v$ is the ZDD for $\mathcal{P}(v_1)$.
If the answer is 0, the path must still choose exactly one edge among $e_2,\dots,e_k$. Thus the 0-child of the $e_1$-node is not terminal, but is exactly the ZDD encoding of the same problem with the first option removed:
$$ \mathcal{P}^{(2)}(v)=\bigcup_{i=2}^k \mathcal{P}_i(v). $$
Continuing inductively, at variable $e_j$, the 1-child corresponds to choosing $e_j$, which yields $\mathcal{P}(v_j)$, while the 0-child passes to the residual problem $\mathcal{P}^{(j+1)}(v)$. At the last edge $e_k$, the 0-child is $\bot$, since failure to choose any outgoing edge is not allowed in a non-sink vertex.
This shows that the ZDD fragment associated with a vertex $v$ is a linear chain of decision nodes:
$$ e_1 \rightarrow e_2 \rightarrow \cdots \rightarrow e_k, $$
where each 0-edge moves to the next decision and each 1-edge branches into the corresponding subtree $\mathcal{P}(v_i)$.
The crucial structural observation is that the “residual problems” $\mathcal{P}^{(j)}(v)$ depend only on the suffix ${e_j,\dots,e_k}$, not on any external context. This is where the in-degree $1$ assumption becomes essential. Since every vertex has a unique incoming edge, each vertex $v$ is reached in exactly one way from its parent. Therefore the subproblem “paths from $v$” is completely determined by $v$ alone. There is no second context that could produce a different ZDD state for the same vertex. Hence every $\mathcal{P}(v)$ corresponds to a unique ZDD node (after reduction), and likewise every $\mathcal{P}^{(j)}(v)$ depends only on the pair $(v,j)$.
Now consider reduction. ZDD reduction merges identical subgraphs and deletes nodes whose 0-child and 1-child are identical. In the present construction, the nodes along the $e_1,e_2,\dots,e_k$ chain have distinct 1-children (namely $\mathcal{P}(v_1),\dots,\mathcal{P}(v_k)$) and distinct 0-children (namely the successive residual states). Therefore no deletion occurs within this chain. However, the important effect is sharing: whenever two vertices $v$ and $u$ have isomorphic subtrees, the corresponding ZDD nodes for $\mathcal{P}(v)$ and $\mathcal{P}(u)$ become identical. Because of in-degree $1$, the subtree rooted at a vertex is a genuine tree structure independent of context, so isomorphism coincides exactly with equality of rooted subtrees in the forest.
We now compare this ZDD structure with the standard binary-tree representation of a forest given by Knuth’s transformation:
$$ \text{first-child}(v) \leftrightarrow \text{left child}, \qquad \text{next-sibling}(v) \leftrightarrow \text{right child}. $$
In that encoding, the children of $v$ form a left-branching spine through first-child pointers, while siblings are linked by right pointers in order.
The ZDD construction produces exactly the same spine, but interpreted as a chain of 0-transitions through the ordered edges $e_1,\dots,e_k$. Each time we move along a 0-edge in the ZDD, we are discarding the current child option and proceeding to the next sibling option. Each time we take a 1-edge, we select that child and move into its independent subproblem $\mathcal{P}(v_i)$. Thus:
The 0-edge in the ZDD corresponds to the next-sibling pointer in the binary-tree encoding, since it advances from $e_j$ to $e_{j+1}$. The 1-edge corresponds to the first-child pointer, since it moves from $v$ via $e_i$ into the subtree rooted at $v_i$.
Formally, define a mapping $\Phi$ from vertices of the binary-tree encoding to ZDD nodes by $\Phi(v)=\mathcal{P}(v)$, and extend it to sibling positions by $\Phi(v,j)=\mathcal{P}^{(j)}(v)$. The recursive definitions
$$ \Phi(v,j) \xrightarrow{0} \Phi(v,j+1), \qquad \Phi(v,j) \xrightarrow{1} \Phi(v_j) $$
match exactly the left-child/right-sibling transitions under the standard encoding.
Because each subproblem $\mathcal{P}(v)$ is uniquely determined by $v$, and because sibling advancement is encoded deterministically by the fixed variable order, this mapping is bijective on reachable states. ZDD reduction does not alter this structure: it only merges identical subtrees, and identical subtrees correspond precisely to identical rooted subforests in the binary-tree representation.
Therefore the reduced ZDD for all source-to-sink paths in a forest is isomorphic to the binary tree obtained from the forest by the left-child/right-sibling transformation. The 1-edges encode first-child descent, the 0-edges encode movement to the next sibling, and ZDD reduction coincides exactly with structural sharing already present in the binary-tree representation.