TAOCP 7.2.2.1 Exercise 30
All such trees can arise as backtrack trees of Algorithm X.
Section 7.2.2.1: Dancing Links
Exercise 30. [23] Continuing exercise 29, let $T$ be a tree in which certain leaves have been distinguished from the others and designated as "solutions." Can all such trees arise as backtrack trees in Algorithm X?
Verified: no
Solve time: 2m29s
Solution
All such trees can arise as backtrack trees of Algorithm X.
Let $T$ be a rooted tree whose leaves are divided into two classes, the distinguished leaves called solutions and the remaining leaves called failures. We construct an exact cover instance whose search tree under Algorithm X with the MRV heuristic is exactly $T$.
The construction used in exercise 29 is modified only at the terminal nodes. For every internal vertex $v$ of $T$, introduce an item $i_v$. For every child $w$ of $v$, introduce an option $O_{v,w}$ containing $i_v$ together with the auxiliary items specified by the construction of exercise 29 that force the continuation of the search to be the subtree rooted at $w$. The auxiliary items belonging to different vertices are disjoint. The construction in exercise 29 guarantees that, after the choice of $O_{v,w}$, the remaining exact cover problem is precisely the subproblem associated with $w$, and that the MRV rule selects the item corresponding to the next vertex of the tree.
For a distinguished solution leaf $s$, the associated terminal subproblem contains no items. Therefore Algorithm X reaches step X1, finds that no items remain, and terminates successfully.
For a nondistinguished leaf $f$, the associated terminal subproblem is changed from the solution terminal condition by adding one fresh item $z_f$ and no option containing $z_f$. At this terminal node, $z_f$ is the only uncovered item, so step X2 of Algorithm X applies and the search terminates unsuccessfully. No option in any other part of the construction contains $z_f$, so the added item cannot affect any earlier node of the search tree.
It remains to prove that the modification preserves the required branching structure. Consider an internal vertex $v$. By the construction from exercise 29, the active options involving the MRV-selected item at $v$ are exactly the options $O_{v,w}$ where $w$ ranges over the children of $v$. Choosing $O_{v,w}$ removes every option belonging to the other branches and leaves the residual instance attached to $w$. The extra terminal item introduced for a failure leaf is created only after the corresponding branch has been selected, and therefore it cannot change the set of active options or the MRV choice at any ancestor of that leaf. Hence every internal vertex of $T$ has exactly the children prescribed by $T$.
Conversely, every leaf reached by Algorithm X corresponds to a leaf of $T$. If the leaf of $T$ is distinguished, all items in its residual instance have been covered and Algorithm X terminates successfully. If the leaf is not distinguished, the residual item $z_f$ remains uncovered and has no active options, so Algorithm X terminates unsuccessfully. Thus the successful leaves and unsuccessful leaves of the search tree are exactly the prescribed distinguished and nondistinguished leaves of $T$.
Therefore every rooted tree with an arbitrary designation of some leaves as solutions can occur as the backtrack tree of Algorithm X with the MRV heuristic. This completes the proof.
∎