TAOCP 7.1.4 Exercise 33

Section 7.1.4: Binary Decision Diagrams

Exercise 33. ▶ [M22] [M22] Specialize exercise 31 so that we can efficiently compute  f(x)=1 (w1x1 + · · · + wnxn) and  f(x)=1 (w1x1 + · · · + wnxn)2 from the BDD of a Boolean function f(x) = f(x1, . . . , xn).

7.1.4 BINARY DECISION DIAGRAMS 261

Verified: no
Solve time: 2m48s

---

Solution

Let the BDD represent $f(x_1,\dots,x_n)$ with variable order $x_1 < x_2 < \cdots < x_n$. For each node $u$ let $V(u)=j$ denote its variable index, and let its LO and HI successors be $u_0$ and $u_1$ respectively. The sink nodes are $\bot$ and $\top$.

The computation required is over all assignments $x$ such that $f(x)=1$. For each node $u$ we associate three quantities over the subfunction represented at $u$:

$$ A_u = \sum_{x \in \mathrm{Sat}(u)} 1,\quad S_u = \sum_{x \in \mathrm{Sat}(u)} \sum_{k=1}^n w_k x_k,\quad Q_u = \sum_{x \in \mathrm{Sat}(u)} \left(\sum_{k=1}^n w_k x_k\right)^2, $$

where $\mathrm{Sat}(u)$ denotes the set of full assignments consistent with $u$ that evaluate to $\top$.

If $V(u)=j$, then variables $x_1,\dots,x_{j-1}$ are already fixed by the path to $u$, while $x_j,\dots,x_n$ remain free. All recurrences must account for this remaining freedom.

For an internal node $u$, the decomposition of assignments according to $x_j$ yields disjoint unions of satisfying sets:

$$ \mathrm{Sat}(u)=\mathrm{Sat}(u_0)\ \cup\ {x_j=1}\times \mathrm{Sat}(u_1). $$

The LO branch corresponds to $x_j=0$ and contributes no $w_j$ term, while the HI branch corresponds to $x_j=1$ and contributes $w_j$ in every assignment.

This gives the counting recurrence

$$ A_u = A_{u_0} + A_{u_1}. $$

For the linear sum, splitting by cases of $x_j$ yields

$$ S_u = S_{u_0} + \left(S_{u_1} + w_j A_{u_1}\right), $$

since every assignment in the HI branch acquires an additional contribution $w_j$.

For the quadratic sum, expand

$$ \left(w_j + \sum_{k>j} w_k x_k\right)^2 = w_j^2 + 2w_j \sum_{k>j} w_k x_k + \left(\sum_{k>j} w_k x_k\right)^2 $$

on the HI branch, while the LO branch contributes only the last term. Summing over satisfying assignments gives

$$ Q_u = Q_{u_0} + \left(Q_{u_1} + 2w_j S_{u_1} + w_j^2 A_{u_1}\right). $$

These recurrences determine $(A_u,S_u,Q_u)$ for every internal node from its children.

It remains to initialize the sinks. Let $u=\bot$. No assignment satisfies the function at $\bot$, hence

$$ A_{\bot}=0,\quad S_{\bot}=0,\quad Q_{\bot}=0. $$

Let $u=\top$ and $V(u)=j$. Then every assignment of the remaining variables $x_j,\dots,x_n$ is satisfying, so $A_{\top}=2^{n-j+1}$. For the linear sum, each variable $x_k$ with $k\ge j$ contributes $w_k$ in exactly half of these assignments, so

$$ S_{\top} = \sum_{k=j}^n w_k \cdot 2^{n-j}. $$

For the quadratic sum, expand the square over all $2^{n-j+1}$ assignments. Each $x_k$ equals $1$ in exactly $2^{n-j}$ assignments, and each product $x_i x_k$ with $i<k$ equals $1$ in exactly $2^{n-j-1}$ assignments. Hence

$$ Q_{\top} = 2^{n-j} \sum_{k=j}^n w_k^2 + 2^{n-j-1} \cdot 2 \sum_{j \le i < k \le n} w_i w_k, $$

which simplifies to

$$ Q_{\top} = 2^{n-j}\left(\sum_{k=j}^n w_k^2 + \sum_{j \le i < k \le n} w_i w_k\right). $$

All values for internal nodes are obtained by a single bottom-up traversal of the BDD with memoization exactly as in the evaluation scheme of exercise 31, storing triples $(A_u,S_u,Q_u)$ per node and computing each node once.

At the root node $r$, the required quantities are $S_r$ and $Q_r$.

This completes the construction. ∎

$$ \boxed{S_r,\ Q_r \text{ computed by the above recurrences on the BDD}} $$