TAOCP 7.1.4 Exercise 9
Let the BDD of $f(x_1,\ldots,x_n)$ be given in the sequential form of (8), with nodes $k_j$ labeled by $V(k_j)=x_j$, LO successor $\operatorname{LO}(k_j)$, HI successor $\operatorname{HI}(k_j)$, and s...
Section 7.1.4: Binary Decision Diagrams
Exercise 9. [16] [16] Given the BDD for a function f(x) = f(x1, . . . , xn), represented sequentially as in (8), explain how to determine the lexicographically largest x such that f(x) = 0.
Verified: no
Solve time: 4m17s
Solution
Let the BDD of $f(x_1,\ldots,x_n)$ be given in the sequential form of (8), with nodes $k_j$ labeled by $V(k_j)=x_j$, LO successor $\operatorname{LO}(k_j)$, HI successor $\operatorname{HI}(k_j)$, and sinks $\bot,\top$.
A vector $x=(x_1,\ldots,x_n)$ satisfies $f(x)=0$ exactly when the evaluation path starting at the root reaches $\bot$. Hence the problem is to find a root-to-$\bot$ path whose induced assignment is lexicographically largest.
Lexicographic order on ${0,1}^n$ is determined by the first coordinate where two strings differ, with $1>0$. Therefore, at the first variable where a choice is available, assigning $x_j=1$ dominates assigning $x_j=0$ whenever both choices still permit completion to a $\bot$-reachable state.
To test feasibility of completion, define for every node $u$ the predicate $R(u)$, meaning that there exists a directed path from $u$ to $\bot$ in the BDD. The definition satisfies $R(\bot)=\text{true}$ and $R(\top)=\text{false}$. For every branch node $u$ with successors $u_0=\operatorname{LO}(u)$ and $u_1=\operatorname{HI}(u)$, a path from $u$ to $\bot$ exists if and only if at least one successor admits such a path, hence
$$ R(u)=R(u_0)\lor R(u_1). $$
Because the BDD is ordered, all arcs go from $k_i$ to $k_j$ with $i<j$. Thus the underlying graph is acyclic with respect to increasing indices, and $R(u)$ can be computed in reverse order of indices, starting from sinks and proceeding downward until the root.
After all values $R(u)$ are computed, construct the assignment $x$ by a single descent from the root. At a node $u=k_j$, the variable $x_j$ is determined as follows. If $R(\operatorname{HI}(u))$ holds, then there exists a completion to $\bot$ after setting $x_j=1$, so set $x_j=1$ and move to $\operatorname{HI}(u)$. Otherwise $R(\operatorname{LO}(u))$ must hold whenever any zero of $f$ is reachable from $u$, so set $x_j=0$ and move to $\operatorname{LO}(u)$.
The resulting vector is lexicographically largest among all $x$ with $f(x)=0$, since any alternative solution must differ at the first index $j$ where it deviates, and replacing $0$ by $1$ at that position preserves reachability to $\bot$ exactly when the construction allows it via $R(\operatorname{HI}(u))$. Therefore no lexicographically larger feasible assignment exists, and the constructed assignment is maximal in lexicographic order.
This completes the construction and justification. ∎