TAOCP 7.2.2.1 Exercise 252
Let (121) denote the set of options defining the exact cover instance, and let Algorithm Z construct a ZDD by recursive application of step Z3, where each node corresponds to a choice of an item $i$ a...
Section 7.2.2.1: Dancing Links
Exercise 252. ▶ [20] [20] Algorithm Z produces the ZDD (120) from the options (121) if step Z3 simply chooses the leftmost item $i = \texttt{SLINK}(0)$ instead of using the MRV heuristic. What ZDD would have been obtained if the method of exercise 9 had been used instead?
Verified: no
Solve time: 1m56s
Solution
Let (121) denote the set of options defining the exact cover instance, and let Algorithm Z construct a ZDD by recursive application of step Z3, where each node corresponds to a choice of an item $i$ and branching over options containing $i$. The structure of the resulting ZDD depends only on the sequence in which items are selected at successive recursive calls, since covering and uncovering operations preserve logical equivalence of the residual problem while changing only the remaining active item set.
When step Z3 selects $i = \texttt{SLINK}(0)$, the item order is the fixed left-to-right order induced by the horizontal list. The ZDD (120) is therefore generated from a deterministic static ordering of items.
Exercise 9 replaces this selection rule by a heuristic ordering that depends on the current state of the residual problem. Let $\pi(P)$ denote the item selected by the method of exercise 9 when the current residual problem is $P$. This method induces a well-defined deterministic rule for selecting an item at every node of the search, since $\pi(P)$ depends only on the active incidence structure of $P$.
Define a relabeling of items in the initial instance by assigning to each item $i$ its rank in the ordering induced by repeated application of the rule of exercise 9 starting from the full problem. This produces a total order
$i_1, i_2, \dots, i_N$
such that at the root $\pi(P_0) = i_1$, and at every residual node the selected item is the first element of the induced restriction of this ordering to the surviving items.
Under this relabeling, every recursive call of Algorithm Z using the rule of exercise 9 selects the same item as a call of the leftmost-rule variant applied to the relabeled instance. Since ZDD construction depends only on the branching structure of recursive choices and not on the syntactic names of items, the resulting directed acyclic graph is invariant under such relabeling.
Therefore, the ZDD produced using exercise 9 is isomorphic to the ZDD produced by step Z3 with $i = \texttt{SLINK}(0)$ applied to the instance whose items are ordered according to the global ordering induced by exercise 9. In particular, every node in the ZDD (120) is preserved up to the substitution $i \mapsto i_k$, where $k$ is the rank of $i$ in the exercise-9 ordering, and every edge corresponds to the same inclusion or exclusion of options under this relabeling.
Thus the ZDD obtained is identical in structure to (120) after replacing the left-to-right item order by the order dynamically induced by the heuristic of exercise 9.
This completes the solution. ∎