TAOCP 7.1.4 Exercise 258

Let $f$ be a Boolean function on variables $x_1,\dots,x_k$ and let its BDD be ordered with $x_1 < x_2 < \cdots < x_k$.

taocpmathematicsalgorithmsvolume-4medium

Section 7.1.4: Binary Decision Diagrams

Exercise 258. ▶ [25] [25] Given a positive integer n, what is the minimum size of a BDD that has exactly n solutions? Answer this question also for a ZDD of minimum size.

Verified: no
Solve time: 1m10s

Solution

Let $f$ be a Boolean function on variables $x_1,\dots,x_k$ and let its BDD be ordered with $x_1 < x_2 < \cdots < x_k$. Let $S(f)$ denote the number of assignments $(x_1,\dots,x_k)\in{0,1}^k$ such that $f=1$. The problem asks for the minimum possible number of nodes in a reduced ordered BDD representing some $f$ with $S(f)=n$.

A BDD has exactly two sink nodes $\bot,\top$. Let $m$ denote the number of branch nodes. The total size is $m+2$.

Each satisfying assignment corresponds to a root-to-$\top$ path obtained by choosing at each level either the LO or HI edge according to the variable value. Distinct assignments induce distinct sequences of edge choices, hence distinct root-to-$\top$ paths in the unrolled decision tree. The BDD is a DAG obtained from this tree by merging identical subfunctions, so the number of distinct root-to-$\top$ paths in the BDD is at most the number of root-to-$\top$ paths in the full binary decision tree induced by $m$ branch nodes.

Each branch node doubles the number of possible partial path extensions in the unfolding, so a BDD with $m$ branch nodes has at most $2^m$ distinct root-to-sink paths. Since each satisfying assignment yields at least one such path, $n \le 2^m$, hence $m \ge \lceil \log_2 n \rceil$.

A matching construction is obtained by taking $k=\lceil \log_2 n\rceil$ variables and defining $f(x_1,\dots,x_k)=1$ if and only if the binary number $(x_1\cdots x_k)_2 < n$. This comparison function is implemented by a lexicographic chain BDD: at each level $i$, the node compares the prefix $(x_1,\dots,x_i)$ against the corresponding prefix of $n$ and proceeds to a sink when a strict decision is forced. The structure is a single chain of $k$ branch nodes, and all terminal outcomes reduce to the two sinks $\bot,\top$. This BDD has exactly $k$ branch nodes and realizes exactly $n$ satisfying assignments by construction.

Thus the minimum number of branch nodes is $\lceil \log_2 n\rceil$, and the minimum total number of nodes is $\lceil \log_2 n\rceil + 2$.

The same argument applies to ZDDs since the structure still reduces any representation of $n$ distinct solutions to at least one binary decision per information bit needed to distinguish $n$ cases, and the lexicographic chain construction carries over without increase in asymptotic structure.

For ZDDs, a chain encoding subsets of a universe of size $k$ selecting exactly the first $n$ subsets in lexicographic order yields a reduced ZDD with $k$ decision nodes and two sinks, again with $k=\lceil \log_2 n\rceil$.

Therefore both models achieve the same minimum.

$$ \boxed{\text{BDD minimum size} = \lceil \log_2 n\rceil + 2,\quad \text{ZDD minimum size} = \lceil \log_2 n\rceil + 2} $$