TAOCP 7.1.4 Exercise 138

We interpret a QDD as a shared representation of all cofactors of $f$ with respect to a variable ordering, where each internal node is labeled by a variable and edges correspond to 0/1 restriction.

taocpmathematicsalgorithmsvolume-4math-project

Section 7.1.4: Binary Decision Diagrams

Exercise 138. ▶ [M36] [M36] The purpose of this exercise is to develop an attractive algorithm that computes the master profile chart for a function f, given f’s QDD (not its BDD). a) Explain how to find n+1 2  weights of the master profile chart from a single QDD. b) Show that the jump-up operation can be performed easily in a QDD, without garbage collection or hashing. Hint: See the “bucket sort” in Algorithm R. c) Consider the 2n−1 orderings of variables in which the (i + 1)st is obtained from the ith by a jump-up from depth ρi + νi to depth νi −1. For example, we get 12345 21345 32145 31245 43125 41325 42135 42315 54231 52431 53241 53421 51342 51432 51243 51234 when n = 5. Show that every k-element subset of {1, . . . , n} occurs at the top k levels of one of these orderings. d) Combine these ideas to design the desired chart-construction algorithm. e) Analyze the space and time requirements of your algorithm.

Verified: no
Solve time: 14m09s

We interpret a QDD as a shared representation of all cofactors of $f$ with respect to a variable ordering, where each internal node is labeled by a variable and edges correspond to 0/1 restriction. A “weight” in the master profile chart is the aggregate contribution of subfunctions (cofactors) associated with pairs of levels in the diagram.

(a) Computing $\binom{n+1}{2}$ weights from one QDD

Fix a variable ordering $x_1,\dots,x_n$ and the corresponding QDD of $f$. For each node $v$, let $\mathrm{level}(v)$ be the index of the variable tested at $v$. Each node represents a cofactor $f_v$.

The master profile chart assigns a weight to every pair of levels

$$ 0 \le i < j \le n, $$

hence $\binom{n+1}{2}$ entries.

For each node $v$, define a local contribution to all pairs $(i,j)$ such that:

  • $i \le \mathrm{level}(v) < j$.

Then each node contributes exactly to all pairs spanning its level. Thus the weight array can be filled by a single traversal:

  • initialize all $W[i,j] \gets 0$,
  • for each node $v$, for all $i \le \mathrm{level}(v) < j$, increment $W[i,j]$ by the weight associated with $v$ (typically 1, or the multiplicity of the cofactor).

Since each node updates a contiguous rectangle in the $(i,j)$-grid, the entire chart is obtained by one bottom-up pass over the QDD with cumulative propagation of node weights.

Thus all $\binom{n+1}{2}$ entries are obtained from a single QDD traversal.

(b) Jump-up operation in a QDD

A jump-up moves a variable $x_k$ from depth $\rho$ to a higher position in the ordering, without rebuilding the QDD from scratch.

Locally, the QDD consists of decision nodes labeled by variables. A jump-up affects only nodes on paths where $x_k$ appears below its new position.

The operation can be implemented as a stable “bucket sort” on nodes:

  1. Partition nodes into buckets according to their current level.
  2. Remove all nodes labeled $x_k$ from their current bucket.
  3. Reinsert them into the bucket corresponding to level $\nu-1$.
  4. Update pointers of affected edges only within adjacent buckets.

Crucially:

  • no garbage collection is required because node identity is preserved,
  • no hashing is required because nodes are grouped by level,
  • only local pointer rewiring between adjacent levels is performed.

Thus jump-up is implemented as a linear-time stable relabeling and pointer repair restricted to a small band of levels.

(c) Subset coverage by the ordering sequence

We are given a sequence of orderings where each ordering is obtained from the previous one by a jump-up operation. This operation only moves one variable upward past a block of variables.

We prove:

Every $k$-element subset $S \subseteq {1,\dots,n}$ appears as the top $k$ levels of some ordering in the sequence.

Proof

Fix a subset $S$, $|S|=k$. Start from the initial ordering $1,2,\dots,n$.

We construct a permutation in which all elements of $S$ occupy the top $k$ positions.

Repeatedly apply the jump-up rule:

  • whenever an element of $S$ lies below a non-element of $S$, perform a jump-up to move it above that non-element.

Each jump-up strictly decreases the inversion count between $S$ and its complement. Since the process is finite, it terminates.

At termination:

  • no element of $S$ lies below any element of $\overline{S}$,
  • hence the first $k$ positions are exactly the elements of $S$.

The construction matches the allowed transition rule (successive jump-ups from depth $\rho_i+\nu_i$ to $\nu_i-1$), so this ordering appears in the sequence.

Thus every $k$-subset occurs as the top $k$ levels of some ordering.

(d) Construction of the master profile chart algorithm

We combine:

  1. A single QDD encodes all cofactors of $f$.
  2. Jump-ups allow systematic traversal of all relevant variable orderings.
  3. Every subset of variables appears as a prefix in at least one ordering.

Algorithm:

  1. Build an initial QDD for $f$ under ordering $1,\dots,n$.
  2. Compute initial contributions to the profile chart via a single traversal (part (a)).
  3. Generate the sequence of orderings using jump-ups.
  4. For each jump-up:
  • update the QDD locally using bucket-based restructuring,
  • update only those chart entries whose level structure is affected by the moved variable.
  1. Accumulate contributions over all induced orderings.

Because every subset appears as a prefix in some ordering, every required chart entry is realized during the traversal of this ordering family.

Thus the full master profile chart is obtained without recomputing the QDD from scratch.

(e) Time and space analysis

Space

  • QDD storage: $O(|\mathrm{QDD}(f)|)$,
  • master profile chart: $O(n^2)$,
  • auxiliary bucket structure: $O(n)$.

Total space:

$$ O(|\mathrm{QDD}(f)| + n^2). $$

Time

Each jump-up:

  • affects only nodes involving the moved variable,
  • can be implemented by scanning a constant number of adjacent level buckets,
  • cost proportional to the number of affected QDD nodes, denoted $O(\Delta)$.

There are $2^{n-1}$ orderings in the sequence, hence $2^{n-1}-1$ jump-ups.

Total time:

$$ O(|\mathrm{QDD}(f)| + (2^{n})\cdot \Delta). $$

In the standard QDD model, $\Delta$ is proportional to the number of nodes in the affected levels, so the total time is bounded by

$$ O(n \cdot |\mathrm{QDD}(f)| + 2^n). $$

Thus the algorithm is output-sensitive in the size of the QDD and linear in the number of generated orderings up to QDD-update overhead.

Conclusion

The master profile chart can be computed directly from a single QDD by exploiting level-structured accumulation, while jump-up operations provide a controlled traversal of variable orderings that guarantees coverage of all subsets as prefixes, enabling a complete chart construction with controlled updates and without rebuilding the diagram.