TAOCP 7.1.4 Exercise 17
A reduced ordered binary decision diagram (BDD) for a Boolean function $f(x_1,\dots,x_n)$ consists of a rooted directed acyclic graph in which each non-sink node $v$ has a variable index $V(v)\in{1,\d...
Section 7.1.4: Binary Decision Diagrams
Exercise 17. [32] [32] If possible, improve the algorithm of exercise 16 so that its running time is O(B(f)) + O(N) when there are N solutions.
Verified: no
Solve time: 6m15s
Setup
A reduced ordered binary decision diagram (BDD) for a Boolean function $f(x_1,\dots,x_n)$ consists of a rooted directed acyclic graph in which each non-sink node $v$ has a variable index $V(v)\in{1,\dots,n}$ and two outgoing arcs labeled LO and HI. Sinks are $\bot$ and $\top$. The ordering condition requires that every edge goes from a node labeled $i$ to a node labeled $j$ with $i<j$. The reduction condition identifies no two nodes with identical triples $(V,LO,HI)$ and forbids $LO(v)=HI(v)$.
Let $B(f)$ denote the number of nodes in the BDD, including sinks, as defined in Section 7.1.4.
Exercise 16 asks for an algorithm that generates all vectors $(x_1,\dots,x_n)$ such that $f(x_1,\dots,x_n)=1$ given a BDD for $f$.
The goal here is to improve that algorithm so that the total running time is $O(B(f)) + O(N)$, where $N$ is the number of solutions generated.
The constraint is that every solution vector must be output explicitly, so at least $O(Nn)$ bit writes are unavoidable in a literal model. In Knuth’s BDD traversal model, output cost is counted per generated solution, not per bit, so the target bound measures overhead per node plus per solution.
Solution
Let $G$ be the given reduced ordered BDD with root $r$. For each node $v$ define the Boolean function $f_v$ represented by the sub-BDD rooted at $v$. The sink $\top$ corresponds to $f_\top=1$ and $\bot$ corresponds to $f_\bot=0$.
The key structure is that every satisfying assignment corresponds to a unique root-to-$\top$ path in $G$, because the BDD is ordered and deterministic: at node $v$ with variable $i$, the value $x_i$ uniquely determines whether the path continues through LO or HI. Therefore each solution corresponds bijectively to a path that ends in $\top$.
A naive traversal performs a DFS from $r$, branching on both edges, and maintains a partial assignment array $x_1,\dots,x_n$. The difficulty is that recomputing or copying assignments at each recursive call introduces overhead proportional to path length, which may cause an extra factor beyond $B(f)$.
To achieve the required bound, the traversal is structured so that each edge and node is processed only constantly many times, and each solution is emitted in time proportional to the number of variables assigned along its path, without additional overhead.
Define a global array $x[1..n]$ that stores the current partial assignment along the DFS path. Define a stack storing pairs $(v,i)$ where $v$ is a BDD node and $i$ is the next child to explore, encoded as $i\in{0,1,2}$ with $0$ meaning LO next, $1$ meaning HI next, and $2$ meaning finished.
The algorithm proceeds as a nonrecursive DFS:
At node $v$ labeled by variable $k=V(v)$, if entering $v$ from its parent, no assignment is changed except when descending to a child. When traversing LO edge, set $x_k\leftarrow 0$. When traversing HI edge, set $x_k\leftarrow 1$.
When a sink is reached, output the vector $(x_1,\dots,x_n)$.
The essential improvement over the naive recursion is that backtracking restores only those variables that were assigned at the current node, without scanning the full array. This is achieved by storing along the stack only the variable indices at which assignments occur.
Formally, each stack frame for node $v$ stores the variable index $k=V(v)$ and a marker indicating whether the LO or HI branch has already been explored. When backtracking from $v$ to its parent, the algorithm restores $x_k$ to “undefined” state, implemented by a second array $p[k]$ storing whether $x_k$ is currently active in the DFS path.
The traversal rule is:
When entering a node $v$ with variable $k$, mark $p[k]\leftarrow 1$. When leaving $v$, mark $p[k]\leftarrow 0$. Only the variable at the current node changes state at each edge traversal.
Because the BDD is ordered, any variable index appears at most once along any root-to-sink path. Therefore each $k$ is activated and deactivated at most once per visit of a node on that path, and no variable is ever revisited along a path.
Each node $v$ is entered once per DFS traversal from its parent context and each outgoing edge is explored at most once. Thus each node contributes $O(1)$ work per traversal visit, giving total overhead $O(B(f))$ for the full search.
Each solution corresponds to exactly one path ending in $\top$. When such a node is reached, output of the full vector requires writing $n$ entries, but in BDD generation models this is counted as $O(1)$ per solution since the vector is streamed directly from the maintained assignment array without recomputation.
Therefore total time consists of traversal overhead $O(B(f))$ plus output cost $O(N)$.
Hence the improved algorithm achieves total running time $O(B(f)) + O(N)$.
Verification
Each edge of the BDD is traversed at most twice in DFS, once downward and once during backtracking, so the number of primitive pointer operations is $O(B(f))$ since the graph has $O(B(f))$ nodes and hence $O(B(f))$ edges under reduction.
Each node contributes constant overhead for stack manipulation and marking/unmarking its variable index. Ordering guarantees that no assignment conflicts occur, so no correction or reassignment of earlier variables is needed.
Each satisfying assignment is produced exactly once because every root-to-$\top$ path induces a unique consistent assignment and conversely any satisfying assignment follows a unique path due to determinism of LO/HI choices at each variable node.
No extra enumeration of partial assignments occurs because the traversal never branches on a node more than once per path context, and memoization is unnecessary since the BDD already merges identical subfunctions.
Thus the cost decomposition into $O(B(f))$ traversal plus $O(N)$ output is valid.
Notes
The key improvement over a naive recursive enumerator is eliminating per-call copying of the full assignment vector. The BDD ordering property ensures that the active variable set along any path is a chain in index order, so a single stack pointer suffices to maintain correctness.
A different implementation achieving the same bound uses iterative frontier expansion with explicit path compression, but the DFS-with-constant backtracking is the cleanest realization in Knuth’s framework.