TAOCP 7.1.4 Exercise 150
Let $f_1,\dots,f_m$ be Boolean functions represented by a shared reduced ordered BDD, with node set size $B(f_1,\dots,f_m)$ in the sense of Section 7.
Section 7.1.4: Binary Decision Diagrams
Exercise 150. [30] [30] When repeated swaps are used to implement jump-up or jump-down, the intermediate results might be much larger than the initial or final BDD. Show that variable jumps can actually be done more directly, with a method whose worst-case running time is O(B(f1, . . . , fm) + B(f π 1 , . . . , f π m)).
Verified: no
Solve time: 5m08s
Setup
Let $f_1,\dots,f_m$ be Boolean functions represented by a shared reduced ordered BDD, with node set size $B(f_1,\dots,f_m)$ in the sense of Section 7.1.4. Let the variable ordering be $x_1 < x_2 < \cdots < x_n$.
Let $\pi$ be a permutation of ${1,\dots,n}$. The goal is to construct BDDs for the functions $f_1^\pi,\dots,f_m^\pi$, where each $f_i^\pi(x_1,\dots,x_n) = f_i(x_{\pi(1)},\dots,x_{\pi(n)})$, directly in worst-case time
$$ O!\bigl(B(f_1,\dots,f_m) + B(f_1^\pi,\dots,f_m^\pi)\bigr), $$
without performing repeated adjacent swaps that may temporarily inflate intermediate BDD sizes.
Solution
Each node of a reduced ordered BDD represents a subfunction determined by fixing variables above it in the ordering. A permutation of variables changes only the interpretation of levels in the decision structure, not the Boolean values represented by any subfunction.
Let $G$ be the original BDD graph. Construct a new BDD $G^\pi$ by evaluating each node of $G$ once under the new variable ordering and rebuilding reduced structure simultaneously.
Define a procedure $\operatorname{Rebuild}(v)$ for each node $v$ of $G$ that returns the corresponding node in $G^\pi$. The procedure is defined recursively.
If $v$ is a sink node $\perp$ or $\top$, then $\operatorname{Rebuild}(v)=v$.
If $v$ is a branch node labeled by variable $x_j$ with LO child $v_0$ and HI child $v_1$, then the subfunction at $v$ is
$$ f_v = (\neg x_j \wedge f_{v_0}) \vee (x_j \wedge f_{v_1}). $$
Under the permutation, $x_j$ becomes variable $x_{\pi^{-1}(j)}$ in the new ordering. The reconstruction builds the node corresponding to this subfunction by first reconstructing the children:
$$ u_0 = \operatorname{Rebuild}(v_0), \quad u_1 = \operatorname{Rebuild}(v_1). $$
If $u_0 = u_1$, the reduced BDD condition forces $\operatorname{Rebuild}(v)=u_0$, since the function does not depend on $x_j$ after reduction.
Otherwise a new node is created (or reused via a unique table) labeled by the correct variable index in the permuted ordering, with LO pointer $u_0$ and HI pointer $u_1$.
This construction visits each node of the original BDD exactly once, because each call to $\operatorname{Rebuild}(v)$ is memoized: once computed, the result is stored and reused for all incoming references to $v$.
The total number of constructed nodes in $G^\pi$ is exactly $B(f_1^\pi,\dots,f_m^\pi)$, since reduction is enforced at each construction step by merging identical $(\text{variable}, \mathrm{LO}, \mathrm{HI})$ triples.
Thus the algorithm performs one constant-time table lookup and at most one node creation per original node, plus one node creation per new node that survives reduction.
Therefore the total work satisfies
$$ T = O(#\text{nodes in }G + #\text{nodes in }G^\pi) = O!\bigl(B(f_1,\dots,f_m) + B(f_1^\pi,\dots,f_m^\pi)\bigr). $$
This direct construction avoids intermediate BDDs created by repeated swaps, since no intermediate representation is materialized; every node is mapped once under the final ordering.
Verification
Each original node is processed exactly once because the memoization table prevents revisiting any node whose image has already been computed.
Each recursive step performs a constant number of operations aside from recursion: two pointer reads, two recursive calls, and at most one lookup or insertion in the unique table.
Every node created in the output corresponds to a distinct reachable triple $(x_j,u_0,u_1)$ under the reduced ordering rules, so the number of created nodes equals $B(f_1^\pi,\dots,f_m^\pi)$.
No intermediate structure larger than the final BDD is constructed because node creation occurs only in the final representation, and no swap sequence generates transient duplicated subgraphs.
Hence both the input traversal cost and output construction cost bound the total runtime.
Notes
The construction is the BDD analogue of applying a permutation to a DAG with sharing preserved via memoization and canonicalization. The essential fact is that reduction is local to each node creation step, so global consistency of the BDD is maintained without intermediate blowup.