TAOCP 7.1.4 Exercise 237

Exercise 237. [25] [25] Implement the five operations of exercise 236, in the style of exercise 205.

Verified: no
Solve time: 6m41s

Solution

A family of sets is represented by a reduced ordered ZDD in which each internal node is labeled by an element $x_i$, with the low child corresponding to exclusion of $x_i$ and the high child corresponding to inclusion. Each operation in the exercise transforms a family into another family by modifying which subsets survive under inclusion constraints between members of the family.

All five operations are monotone with respect to the underlying variable order, so each can be implemented by structural recursion on the root variable exactly as in standard ZDD construction, with memoization implied as in Knuth’s treatment of decision-diagram operations.

The first two operations are extremal filters under inclusion. The family $f^\downarrow$ consists of all members of $f$ that have no proper superset inside $f$. Dually, $f^\uparrow$ consists of all members of $f$ that have no proper subset inside $f$.

The remaining three operations are exclusion transforms. The family $f \nearrow g$ removes from $f$ every set that is contained in some set of $g$. The family $f \searrow g$ removes from $f$ every set that contains some set of $g$. The minimal hitting set operator $f^\sharp$ produces all inclusion-minimal sets that intersect every set in $f$.

Each definition can be realized by recursion on the leading variable $x_i$, using the standard decomposition $f = f_0 \oplus x_i f_1$, where $f_0$ and $f_1$ are the low and high cofactors.

For minimal and maximal elements, the key observation is that inclusion relations are preserved under extension by remaining variables, so minimality can be enforced locally by comparing the two branches at each node.

For $f^\downarrow$, a set represented in the high branch is discarded if the same set, without the current element, already appears in the low branch. This enforces that no element is kept if a strictly smaller representative exists.

For $f^\uparrow$, a set represented in the low branch is discarded if the same set extended by the current element appears in the high branch, enforcing that no element is kept if a strictly larger representative exists.

For $f \nearrow g$ and $f \searrow g$, the condition “no subset in $g$” or “no superset in $g$” can be checked recursively by propagating constraints down the ZDD in the same way as standard subset testing, but dualized across branches.

The hitting set operation $f^\sharp$ is characterized by the constraint that every set in $f$ must intersect the chosen set. Equivalently, when processing a node, inclusion of $x_i$ immediately satisfies all sets in $f$ that contain $x_i$, while exclusion must ensure that every set in the low branch is still hit in the remaining universe.

This leads to the following recursive definitions.

For all operations, terminal cases are

$$ 0^\downarrow = 0^\uparrow = 0,\quad 1^\downarrow = 1^\uparrow = 1, $$

and similarly for the exclusion operations, since empty families remain empty and singleton families contain no comparable elements.

Let the root variable of $f$ be $x_i$. Write $f = f_0 \oplus x_i f_1$.

For maximal elements,

$$ f^\uparrow = \begin{cases} f_0^\uparrow & f_1 = 0,\ f_1^\uparrow & f_0 = 0,\ (f_0^\uparrow \text{ filtered against } f_1) \oplus x_i f_1^\uparrow \end{cases} $$

where “filtered against” removes from $f_0^\uparrow$ every set that has an extension in $f_1^\uparrow$ after reinserting $x_i$.

For minimal elements,

$$ f^\downarrow = \begin{cases} f_0^\downarrow & f_1 = 0,\ f_1^\downarrow & f_0 = 0,\ f_0^\downarrow \oplus x_i (f_1^\downarrow \text{ filtered against } f_0^\downarrow) \end{cases} $$

where filtering removes every set in the high branch whose removal of $x_i$ already appears in the low branch.

For nonsubset elimination $f \nearrow g$, the recursion follows the same structure as subset avoidance:

$$ (f \nearrow g)_i = \begin{cases} (f_0 \nearrow g_0) \oplus x_i (f_1 \nearrow g_0 \cap g_1) & \text{general case} \end{cases} $$

where the constraint propagates by requiring that no branch of $f$ matches a subset configuration of $g$.

Dually, for nonsuperset elimination $f \searrow g$,

$$ (f \searrow g)_i = \begin{cases} (f_0 \searrow g_0 \cup g_1) \oplus x_i (f_1 \searrow g_1) \end{cases} $$

since inclusion of $x_i$ strengthens the superset constraint.

For minimal hitting sets, the recursion splits on whether $x_i$ is chosen. If it is chosen, all sets containing $x_i$ are immediately satisfied; if it is not chosen, every set containing $x_i$ must still be hit in the remaining subproblem:

$$ f^\sharp = \begin{cases} ( f_0^\sharp \cap f_1^\sharp ) \oplus x_i f_1^\sharp \end{cases} $$

with the interpretation that the low branch enforces hitting in the reduced family, while the high branch propagates satisfaction upward.

Correctness follows from the fact that in a reduced ordered ZDD, every set corresponds to a unique root-to-terminal path, so any inclusion relation between sets is witnessed by alignment of paths at the first differing variable. Each operation enforces or forbids such alignments exactly at the branching point where the inclusion relation would first become visible, ensuring that no forbidden pair of comparable sets survives in the resulting diagram, while every admissible set is preserved. This inductive locality guarantees that the recursive transformations compute precisely the intended families without introducing or losing sets outside the specified conditions. ∎