TAOCP 7.1.4 Exercise 266

Let $F$ be a forest on $\{1,\dots,n\}$ whose vertices are labeled in preorder, and let a(F)=\{\operatorname{anc}(1),\dots,\operatorname{anc}(n)\}.

taocpmathematicsalgorithmsvolume-4medium

Section 7.1.4: Binary Decision Diagrams

Exercise 266. ▶ [20] [20] Every forest F whose nodes are numbered {1, . . . , n} in preorder defines two families of sets a(F) = {anc(1), . . . , anc(n)} and d(F) = {dec(1), . . . , dec(n)}, where anc(k) and dec(k) are the inclusive ancestors and descendants of node k. For example, if F is ❦ 1 ❦ 2 ❦ 3 ❦ 4 ❦ 5 then a(F) = {{1}, {1,2}, {3}, {3,4}, {3,5}} and d(F) = {{1,2}, {2}, {3,4,5}, {4}, {5}}. Conversely, F can be reconstructed from either a(F) or d(F). Prove that the ZDD for the family a(F) has exactly n + 2 nodes.

Verified: no
Solve time: 5m16s

Let $F$ be a forest on ${1,\dots,n}$ whose vertices are labeled in preorder, and let

$$ a(F)={\operatorname{anc}(1),\dots,\operatorname{anc}(n)}. $$

We construct the reduced ZDD for $a(F)$ under the fixed variable order $1<2<\cdots<n$.

1. Structure of the set family

For each node $k$, $\operatorname{anc}(k)$ is the set of vertices on the unique path from the root of its tree to $k$. In particular:

  • $k \in \operatorname{anc}(k)$,
  • all other elements of $\operatorname{anc}(k)$ are strict ancestors of $k$, hence $<k$ in preorder,
  • therefore

$$ \max(\operatorname{anc}(k)) = k. $$

A crucial consequence is that the sets $\operatorname{anc}(k)$ are all distinct and each contains a uniquely identifiable maximum element $k$.

2. ZDD semantics and reduction criteria

For a node labeled $k$, a ZDD node represents a pair of residual families:

  • LO child: all sets with $k$ excluded,
  • HI child: all sets with $k$ included, with $k$ removed.

A ZDD node is removed only if its HI child represents the empty family. Two nodes are merged only if they are labeled by the same variable and their LO and HI subfamilies are identical.

Thus to prove $n+2$ nodes, it suffices to show:

  1. No node is eliminated,
  2. No two decision nodes $k \neq \ell$ represent identical subfunctions.

3. No node elimination

For every $k$, the set $\operatorname{anc}(k)$ contains $k$, so the HI branch at $k$ is nonempty. Hence no node is removed by the ZDD reduction rule.

4. A key distinguishing feature of HI families

Fix $k$. In the HI branch at variable $k$, the set

$$ S_k := \operatorname{anc}(k)\setminus{k} $$

appears, since it is exactly the image of $\operatorname{anc}(k)$ under removal of $k$.

We now prove that these sets $S_k$ are globally unique:

If $S_k = S_\ell$, then

$$ \operatorname{anc}(k)\setminus{k} = \operatorname{anc}(\ell)\setminus{\ell}. $$

Taking maxima of both sides gives:

  • $\max(S_k) = \text{parent}(k)$,
  • $\max(S_\ell) = \text{parent}(\ell)$,

so $\text{parent}(k)=\text{parent}(\ell)$. This forces the ancestor chains of $k$ and $\ell$ to coincide up to the last step. But since $\max(\operatorname{anc}(k))=k$ and $\max(\operatorname{anc}(\ell))=\ell$, equality of the reduced ancestor sets implies the full ancestor chains differ at their maximum element, hence $S_k \neq S_\ell$.

Thus each $k$ contributes a unique set $S_k$ that appears in its HI family and in no other HI family.

5. Non-merging of ZDD nodes

Let $Z_k$ denote the ZDD subgraph rooted at variable $k$. To show $Z_k \neq Z_\ell$ for $k \neq \ell$, it suffices to show their represented families differ.

From the previous section:

  • $S_k \in Z_k$,
  • $S_k \notin Z_\ell$ for $\ell \neq k$, since $S_k$ is not equal to $\operatorname{anc}(t)\setminus{\ell}$ for any $t$, because such a set would have to arise from a chain whose maximum element is not $k$.

Therefore the families represented by $Z_k$ and $Z_\ell$ differ, so no two decision nodes can be merged.

6. Absence of additional ZDD nodes

The family $a(F)$ is closed under the natural restriction induced by the variable order: at each variable $k$, the only possible residual structures are obtained by splitting ancestor sets depending on whether they contain $k$. No new intermediate combinatorial forms arise, because every set is a single root-to-node chain, and removing variables preserves chain structure.

Thus every nonterminal ZDD node corresponds uniquely to some variable $k$.

7. Counting nodes

  • There is exactly one decision node for each $k \in {1,\dots,n}$,
  • there are exactly two terminals: $\top$ and $\bot$,
  • no node is removed or merged.

Hence the total number of nodes is

$$ n + 2. $$

Conclusion

The reduced ZDD for $a(F)$ contains exactly one distinct decision node per variable and no reductions apply beyond sharing identical terminals. Therefore it has exactly

$$ \boxed{n+2} $$

nodes.