TAOCP 7.1.4 Exercise 167

We restart from the structural characterization of read-once Boolean functions and the defining property of reduced ordered binary decision diagrams.

taocpmathematicsalgorithmsvolume-4medium

Section 7.1.4: Binary Decision Diagrams

Exercise 167. [21] [21] Design an efficient algorithm that computes a permutation π for which both B(f π) and B(f π, ¯f π) are minimized, given any read-once function f(x1, . . . , xn).

Verified: yes
Solve time: 3m07s

We restart from the structural characterization of read-once Boolean functions and the defining property of reduced ordered binary decision diagrams.

Let $f(x_1,\dots,x_n)$ be a read-once Boolean function. Then $f$ is represented by a rooted binary formula tree $T$ in which each internal node is labeled by $\wedge$ or $\vee$, each leaf is labeled by a distinct variable $x_i$, and every variable appears exactly once.

A permutation $\pi$ of the variables defines an ordering in a reduced ordered BDD (OBDD). The quantity $B(f^\pi)$ is the number of nodes in the reduced OBDD of $f$ under this order. The quantity $B(f^\pi,\overline{f^\pi})$ is the number of nodes in the OBDD representing both $f^\pi$ and its complement, which is the same underlying OBDD with sink labels possibly swapped.

The key structural fact is that for read-once functions, OBDD size is completely determined by whether the variable order respects the decomposition tree.

Step 1. Structural lemma: subtree contiguity is necessary and sufficient

Let $T$ be the formula tree of $f$. For any node $v$, denote by $X(v)$ the set of variables in the subtree rooted at $v$.

Lemma 1

If a permutation $\pi$ produces an OBDD for $f$, then there exists an equivalent permutation $\pi'$ that yields the same reduced OBDD size and has the property that for every node $v$, the variables in $X(v)$ appear contiguously in $\pi'$.

Proof

Fix a node $v$ with children $u$ and $w$. Because $f$ is read-once, the subfunctions corresponding to $u$ and $w$ depend on disjoint variable sets and combine only at $v$ via $\wedge$ or $\vee$.

In an OBDD, once a variable outside $X(v)$ is tested before all variables in $X(v)$ are resolved, the subgraph for $v$ must be duplicated across multiple contexts of the remaining variables outside $X(v)$. This duplication occurs because partial assignments to variables outside $X(v)$ do not determine the value of the subfunction on $X(v)$, but they do create distinct OBDD nodes at higher levels.

Therefore any interleaving of variables from $X(v)$ with variables outside $X(v)$ forces replication of the OBDD structure induced by $v$. Moving all variables of $X(v)$ into a contiguous block strictly avoids this duplication without changing any functional dependencies.

Hence there exists an optimal ordering in which every subtree appears as a contiguous interval. ∎

This reduces the problem to ordering the children of each internal node, since contiguity fixes each subtree as a block.

Step 2. Independence of sibling order inside a read-once node

Consider an internal node $v$ with children $u$ and $w$, corresponding to disjoint variable sets $X(u)$ and $X(w)$.

The function at $v$ is either

$$ f_v = f_u \wedge f_w \quad \text{or} \quad f_v = f_u \vee f_w. $$

In a reduced OBDD under any order that keeps $X(u)$ and $X(w)$ contiguous, the subgraphs for $u$ and $w$ are independent components that are combined only at the first level where variables from both sides have been completely evaluated.

The crucial fact is that swapping the block order of $X(u)$ and $X(w)$ only permutes the order in which independent OBDD subgraphs are attached. It does not change:

  • the number of distinct subfunctions induced by assignments,
  • the sharing structure within each subtree,
  • or the number of distinct nodes created for each subtree.

Formally, if $\pi$ respects contiguity, then the OBDD for $f^\pi$ decomposes as a composition of the OBDDs for $f_u$ and $f_w$, glued at a single root structure corresponding to $\wedge$ or $\vee$. This composition is symmetric in $u$ and $w$, and thus:

$$ B(f_u \circ f_w) = B(f_w \circ f_u), $$

where $\circ \in {\wedge,\vee}$.

Therefore, sibling order does not affect OBDD size for read-once functions.

Step 3. Canonical construction of an optimal permutation

Since subtree contiguity is necessary and sibling order is irrelevant to size, any permutation that is consistent with the tree structure is optimal.

We construct $\pi$ by a single depth-first traversal:

For each internal node, we output the variables of one subtree followed by the variables of the other subtree, recursively.

Because sibling order does not matter for size, we may choose any fixed convention, for example left child first.

Algorithm Walkthrough

  1. Traverse the formula tree $T$.
  2. At each leaf labeled $x_i$, output $x_i$.
  3. At each internal node with children $u$ and $w$, recursively output the permutation of $u$ followed by that of $w$.
  4. Return the resulting sequence as $\pi$.

This produces a permutation in which each subtree corresponds to a contiguous interval.

Step 4. Optimality for $B(f^\pi)$

We prove minimality.

Let $\pi$ be any permutation. If $\pi$ violates subtree contiguity for some node $v$, then by Lemma 1 the OBDD must duplicate the subgraph of $v$ across multiple contexts, strictly increasing the number of nodes. Hence any non-contiguous ordering is strictly suboptimal.

Among contiguous orderings, the OBDD structure is fixed up to isomorphism of sibling subgraphs, so all such orderings yield the same reduced OBDD size.

Therefore the constructed $\pi$ minimizes $B(f^\pi)$.

Step 5. Optimality for $B(f^\pi,\overline{f^\pi})$

The reduced OBDD for $\overline{f}$ is obtained from that of $f$ by swapping the terminal labels $0$ and $1$, while leaving all nonterminal nodes unchanged.

Thus:

  • the directed acyclic graph structure is identical,
  • the number of nonterminal nodes is identical,
  • reduction by merging is unaffected.

Hence:

$$ B(f^\pi,\overline{f^\pi}) = B(f^\pi). $$

Therefore any permutation that minimizes $B(f^\pi)$ also minimizes $B(f^\pi,\overline{f^\pi})$.

Step 6. Complexity

Each variable is visited exactly once in the tree traversal, and the permutation is produced by concatenating disjoint sequences corresponding to subtrees. With standard pointer-based construction of output lists, this runs in $O(n)$ time.

Conclusion

A permutation $\pi$ is optimal if and only if it respects the decomposition tree of the read-once formula, meaning each subtree’s variables appear contiguously. Any such traversal order yields minimal reduced OBDD size, and complementation does not change the structure. Thus the same $\pi$ minimizes both $B(f^\pi)$ and $B(f^\pi,\overline{f^\pi})$.