TAOCP 7.2.2.1 Exercise 257

The items are $1,2,\dots,n$.

taocpmathematicsalgorithmsvolume-4medium

Section 7.2.2.1: Dancing Links

Exercise 257. ▶ [20] [20] How does Algorithm Z do on the "extreme" exact cover problem, with $n$ items and $2^n - 1$ options? (See the discussion preceding (82).)

a) What signatures $\sigma$ are formed in step Z2?

b) Draw the schematic ZDD, analogous to (123), when $n = 4$.

Verified: yes
Solve time: 1m53s

Solution

The items are $1,2,\dots,n$. The $2^n-1$ options are all nonempty subsets of ${1,\dots,n}$. An exact cover is a collection of pairwise disjoint nonempty subsets whose union is ${1,\dots,n}$. Every solution is therefore a set partition of ${1,\dots,n}$.

Algorithm Z maintains at each recursive call the set of primary items still uncovered. The signature $\sigma$ in step Z2 is the bit vector of these items, so it represents a subset $S \subseteq {1,\dots,n}$.

(a) Signatures $\sigma$

Each recursive state is determined solely by the set of uncovered items $S$. Since every option is an arbitrary nonempty subset, any transition from $S$ chooses a nonempty subset $T \subseteq S$ as the next option, removing all elements of $T$ from $S$.

Starting from $S_0={1,\dots,n}$, every recursive call replaces $S$ by $S \setminus T$ for some nonempty $T \subseteq S$. Hence every reachable signature is a subset of ${1,\dots,n}$.

Conversely, every subset $S \subseteq {1,\dots,n}$ is reachable by choosing successive singleton options, since ${i}$ is always an available option for each $i$ and the family of options contains all nonempty subsets. Repeated deletion of singletons yields any desired subset.

Thus the set of signatures formed in step Z2 is exactly

${\sigma \subseteq {1,\dots,n}},$

so there are exactly $2^n$ distinct signatures, including the empty signature which corresponds to termination.

This completes part (a).

(b) ZDD for $n=4$

The family represented is

$\mathcal{F}={A \subseteq {1,2,3,4} : A \neq \emptyset}.$

The ZDD for all subsets is the standard subset ZDD over variables $1,2,3,4$, ordered $1<2<3<4$. Reduction eliminates the empty-set path only.

At each node $i$, the 0-edge corresponds to excluding $i$, and the 1-edge corresponds to including $i$. The 1-edge immediately jumps to the terminal $1$-node because once a set is chosen, no further constraints restrict membership in this option family.

The 0-edges propagate to the next variable, since exclusion of $i$ does not force inclusion of any later element.

The resulting reduced structure is:

  • Root node $1$

  • 1-edge to terminal $1$

  • 0-edge to node $2$

  • Node $2$

  • 1-edge to terminal $1$

  • 0-edge to node $3$

  • Node $3$

  • 1-edge to terminal $1$

  • 0-edge to node $4$

  • Node $4$

  • 1-edge to terminal $1$

  • 0-edge to terminal $0$

The path $1 \to 0 \to 0 \to 0 \to 0$ corresponds to the empty set and is the only path reaching terminal $0$. Every other path reaches terminal $1$, corresponding to a nonempty subset.

This directed acyclic structure is the schematic ZDD for $n=4$.

This completes the solution. ∎