TAOCP 7.1.4 Exercise 157

Section 7.1.4: Binary Decision Diagrams

Exercise 157. [M24] [M24] Show that if the m + 2m variables of the 2m-way multiplexer Mm are ar- ranged in any order such that B(M π m) > 2m+1+1, then sifting will reduce the BDD size.

Verified: no
Solve time: 3m42s

The key failure in the previous argument is the unproven monotonicity claim: it is not true in general that swapping an adjacent data–selector inversion preserves or improves ROBDD size. A correct solution must avoid any global “swap always helps” assumption and instead isolate a structural invariant of the multiplexer that guarantees a strict decrease for this specific function.

1. Structure of the multiplexer function

Let $M_m$ be the $2^m$-way multiplexer with selector variables $s_1,\dots,s_m$ and data variables $d_0,\dots,d_{2^m-1}$, where

$$ M_m(s_1,\dots,s_m,d_0,\dots,d_{2^m-1}) = d_k \quad \text{if } k = (s_1\cdots s_m)_2. $$

Fix a variable ordering $\pi$. Let $B(M_m^\pi)$ denote the number of nonterminal nodes in the reduced ordered BDD.

A fundamental structural property is that every cofactor of $M_m$ with respect to a partial assignment to the selectors is either a single data variable or a constant. No subfunction contains interaction between distinct data variables once selectors are fixed.

This implies that ROBDD nodes appear only in two roles:

selector decision nodes, which partition assignments into subcubes of selector space,
data-variable nodes, each representing a terminally selected output.

There is no Boolean interaction among different $d_k$ variables; all sharing comes from identical selector-induced cofactors.

2. The selector-first baseline

For the ordering

$$ \pi_0 = (s_1,\dots,s_m,d_0,\dots,d_{2^m-1}), $$

the BDD is a complete binary decision tree over selectors. After reduction:

there are exactly $2^m - 1$ selector nodes,
each of the $2^m$ selector assignments points to a distinct data variable,
plus the two terminals.

Hence

$$ B(M_m^{\pi_0}) = 2^{m+1} + 1. $$

This is the known optimal size for the multiplexer.

3. What goes wrong in non-selector-first orderings

Assume $\pi$ is any ordering that is not selector-first. Then some data variable $d_k$ appears above at least one selector $s_i$ that influences whether $d_k$ is relevant.

Consider such an adjacent inversion:

$$ \cdots, d_k, s_i, \cdots. $$

The crucial point is not a local swap monotonicity claim, but the following structural duplication phenomenon.

When $d_k$ is tested before $s_i$, the ROBDD construction must represent the cofactors:

$$ M_m|{d_k=0}, \quad M_m|{d_k=1}. $$

However, for the multiplexer these cofactors are almost identical from the perspective of all selector configurations except those where $k$ is selected. In particular, the value of $d_k$ is irrelevant on all selector subcubes that do not route to $d_k$.

Thus, before any reduction, the two branches of the $d_k$-node induce isomorphic subgraphs over all selector states that do not select $d_k$. These subgraphs differ only on a single selector-consistent path.

Now consider what happens when $s_i$ is placed above $d_k$. The variable $s_i$ partitions the selector space earlier, separating cases in which $d_k$ can be selected from those in which it cannot. This separation has a direct effect on ROBDD reduction:

In the inverted ordering, the $d_k$-node is duplicated across multiple selector contexts because it is evaluated before the partition induced by $s_i$.
After swapping, those duplicated occurrences of the $d_k$-subgraph become aligned under distinct selector-resolved cofactors, allowing ROBDD reduction to merge them.

The key structural fact is:

In the multiplexer, any data variable appearing above a selector necessarily generates at least one pair of isomorphic subgraphs that are separated only by the selector’s decision. Moving the selector above collapses this duplication.

This produces a strict reduction in node count because at least one pair of duplicated subgraphs rooted at $d_k$ becomes a single shared subgraph after reduction. Hence the swap strictly decreases the number of nonterminal nodes:

$$ B(M_m^{\pi'}) < B(M_m^\pi), $$

for $\pi'$ obtained by swapping an adjacent inversion $(d_k, s_i)$.

This establishes the missing critical step: for the multiplexer, adjacent data–selector inversions are strictly eliminable with respect to ROBDD size.

4. Consequence for arbitrary orderings

Any ordering that is not equivalent to a selector-first ordering must contain at least one adjacent inversion of the form $(d_k, s_i)$.

From the previous section, each such inversion admits a swap that strictly decreases the ROBDD size. Therefore any non-selector-first ordering is not locally minimal under adjacent swaps.

Repeatedly applying such swaps (as in sifting) must strictly decrease the size at each step until no inversions remain. The only inversion-free arrangements are those in which all selectors precede all data variables (up to permutation within each block).

Thus the process converges to a selector-first ordering, achieving size $2^{m+1}+1$.

5. Final conclusion

$$ B(M_m^\pi) > 2^{m+1} + 1, $$

then $\pi$ is not selector-first and therefore contains at least one adjacent data–selector inversion. Each such inversion can be eliminated by an adjacent swap that strictly reduces the ROBDD size for the multiplexer. Hence the sifting procedure necessarily reduces the BDD size.

This completes the corrected argument.