TAOCP 7.1.4 Exercise 210

Section 7.1.4: Binary Decision Diagrams

Exercise 210. ▶ [23] [23] Given the ZDD for f, show how to construct the ZDD for the function g(x) = [f(x) = 1 and νx = max{νy | f(y) = 1}].

Verified: yes
Solve time: 2m12s

Solution

Let the ZDD for $f$ be given as a reduced ordered ZDD with variable ordering $x_1 < x_2 < \cdots < x_n$. Each root-to-$\top$ path corresponds to a solution $x \in {0,1}^n$ with $f(x)=1$. Let $\nu x$ denote the value associated with a solution $x$, and assume $\nu$ is monotone along inclusion in the sense induced by the ZDD interpretation: when a path includes variable $x_i$ via a HI-arc, it contributes a fixed local increment $\nu(i)$ to the total value, while a LO-arc contributes nothing for $x_i$. Thus every solution $x$ has a well-defined value $\nu x$, obtained as the sum of contributions along its chosen HI-branches.

The function $g$ selects exactly those solutions of $f$ whose value is maximal among all solutions of $f$. Let

$$ M = \max{\nu y \mid f(y)=1}. $$

The goal is to construct the ZDD of the characteristic function of the set ${x \mid f(x)=1 \text{ and } \nu x = M}$.

For every node $u$ of the ZDD of $f$, define a value $W(u)$ as the maximum achievable $\nu$-value among all solutions represented in the sub-ZDD rooted at $u$. If $u=\bot$, no solution exists and $W(\bot)=-\infty$. If $u=\top$, the empty assignment is the only solution and contributes value $0$, so $W(\top)=0$.

If $u$ is a branch node labeled by variable $x_i$ with LO-child $u_0$ and HI-child $u_1$, then every solution represented at $u$ either excludes $x_i$ or includes it. In the first case the best achievable value is $W(u_0)$. In the second case the variable $x_i$ is included and contributes $\nu(i)$ in addition to the best continuation from $u_1$, giving value $\nu(i)+W(u_1)$. Hence

$$ W(u)=\max{W(u_0),\ \nu(i)+W(u_1)}. $$

This recurrence determines $W(u)$ for all nodes by a single bottom-up traversal of the ZDD, since acyclicity guarantees that children are evaluated before parents.

The ZDD for $g$ is constructed by a second traversal that keeps only those arcs that achieve the maximum at each node. For a node $u$ with label $x_i$, LO-child $u_0$, and HI-child $u_1$, define the retained children in the new diagram as follows. The LO-arc is kept if and only if $W(u)=W(u_0)$, in which case it points to the copy of $u_0$ in the new structure. The HI-arc is kept if and only if $W(u)=\nu(i)+W(u_1)$, in which case it points to the copy of $u_1$. If both equalities hold, both arcs are kept; if only one holds, only that arc remains. If neither holds, the node is unreachable from the root in the optimal solution set and is omitted.

Let $G$ denote the resulting reduced ordered ZDD with the same root as the original structure but with all non-maximizing arcs removed and with unreachable nodes deleted.

Every path in $G$ corresponds to a path in the original ZDD of $f$, since only existing arcs are retained. Along each such path, every retained HI-arc contributes exactly the same $\nu$-increment as in the original structure, so the total value of any solution represented in $G$ equals the value computed in the original ZDD. The construction ensures that at every node only transitions preserving the equality $W(u)$ are allowed, so no path in $G$ can decrease the optimal value at any stage, hence every root-to-$\top$ path in $G$ has total value $M$.

Conversely, let $x$ be any solution of $f$ with $\nu x = M$. Along the corresponding path in the original ZDD, at each visited node $u$ the continuation chosen by $x$ must achieve the maximum in the recurrence defining $W(u)$, since otherwise the total value of $x$ would be strictly less than $W(\text{root})=M$. Therefore every arc used by $x$ is retained in $G$, so the path for $x$ is present in the constructed ZDD. Hence every optimal solution of $f$ is represented in $g$.

This establishes that $G$ represents exactly those solutions of $f$ with maximal $\nu$-value, which is precisely the function $g$. This completes the proof. ∎