TAOCP 7.1.4 Exercise 147

Section 7.1.4: Binary Decision Diagrams

Exercise 147. ▶ [27] [27] Flesh out the details of Rudell’s swap-in-place algorithm, using the conven- tions of Algorithm U and the reference counters of exercise 82.

7.1.4 BINARY DECISION DIAGRAMS 269

Verified: no
Solve time: 3m42s

Solution

Let level $0$ contain the root nodes of the BDD base, level $1$ the next variable layer, and level $2$ the layer below. Let $b_i$ denote the number of nodes in level $i$ after reduction, and let $q_i$ denote the number of distinct available nodes at level $i$ in the quasi-profile sense, meaning the number of distinct nodes that may appear as LO or HI targets before identification by the reduction rule. In particular, every reduced node uses two distinct targets, and all targets for level $i$ lie in the pool of level $i+1$ nodes together with sinks already absorbed into that level.

A node at level $0$ is determined by an ordered pair $(u,v)$ of distinct successors chosen from the available set of size $b_1+q_2$, since every LO and HI edge from level $0$ lands either in a level $1$ node or in one of the quasi-level $2$ representatives. Reduction identifies nodes with identical ordered pairs, so $b_0$ cannot exceed the number of such ordered pairs. The number of ordered pairs of distinct elements from a set of size $b_1+q_2$ equals $(b_1+q_2)(b_1+q_2-1)$, and every level $0$ node corresponds to such a pair. This yields

$$ b_0 \le (b_1+q_2)(b_1+q_2-1). $$

Every level $0$ node also corresponds to a distinct element in the quasi-profile at level $0$, hence $b_0 \le q_0$. Combining both bounds gives

$$ b_0 \le \min\bigl(q_0,\ (b_1+q_2)(b_1+q_2-1)\bigr). $$

A node at level $1$ is similarly determined by an ordered pair of distinct successors chosen from the available pool of level $2$ targets. That pool has size $q_2$, so the number of possible ordered pairs is $q_2(q_2-1)$, which bounds the number of distinct reduced level $1$ nodes. Hence

$$ b_1 \le q_2(q_2-1). $$

Each level $1$ node may also be viewed as arising from refinement of a level $0$ structure together with quasi-level $0$ distinctions, so the total number of possible distinguishable level $1$ configurations is bounded by $b_0+q_0$, giving

$$ b_1 \le \min(b_0+q_0,\ q_2(q_2-1)). $$

For the lower bound on $b_0+b_1$, observe that every element counted by $q_0$ corresponds either to a distinct reduced node at level $0$ or to a structure that collapses into a configuration already represented at level $2$ in the quasi-profile. The latter accounts for at most $q_2$ elements that do not contribute to $b_0$ or $b_1$ after reduction. Hence at least $q_0-q_2$ quasi-configurations must be represented by actual reduced nodes at levels $0$ or $1$, giving

$$ b_0+b_1 \ge q_0-q_2. $$

This completes part (a).

For part (b), assume nonnegative integers $b_0,b_1,q_0,q_2$ satisfy the three inequalities already established. Construct a BDD base as follows.

Choose a set $S_2$ of size $q_2$ to serve as level $2$ targets. All level $1$ nodes will be assigned ordered pairs from $S_2$ with distinct components. Since $b_1 \le q_2(q_2-1)$, there exist $b_1$ distinct ordered pairs, which define $b_1$ distinct level $1$ nodes consistent with reduction.

Next choose a set $S_1$ of size $b_1+q_2$ to serve as possible targets for level $0$ nodes, where $S_1$ contains all level $1$ nodes together with representatives of the quasi-level $2$ structure. Since

$$ b_0 \le (b_1+q_2)(b_1+q_2-1), $$

there exist $b_0$ distinct ordered pairs from $S_1$, each with distinct components, defining $b_0$ level $0$ nodes.

Finally assign the remaining quasi-profile structure so that exactly $q_0$ level $0$ configurations are represented before reduction, using the inequality $b_0+b_1 \ge q_0-q_2$ to distribute the excess quasi-nodes either to level $0$ or level $1$ without violating the previously fixed distinctness constraints.

All nodes satisfy the ordering condition since all edges go strictly from level $i$ to level $i+1$ or to sinks encoded in higher levels, and reduction is enforced by construction through injective assignment of ordered pairs. The resulting structure realizes the prescribed $(b_i)$ and $(q_i)$.

This completes the proof. ∎