TAOCP 7.2.2.1 Exercise 83

Section 7.2.2.1: Dancing Links

Exercise 83. ▶ [20] [20] Algorithm C can be extended in the following curious way: Let $p$ be the primary item that is covered first, and suppose that there are $k$ ways to cover it. Suppose further that the $j$th option for $p$ ends with a secondary item $s_j$, where ${s_1, \ldots, s_k}$ are distinct. Modify the algorithm so that, whenever a solution contains the $j$th option for $p$, it leaves items ${s_1, \ldots, s_{j-1}}$ uncovered. (In other words, the modified algorithm will replicate the behavior of the unmodified algorithm on a much larger instance, in which the $j$th option for $p$ contains all of $s_1, s_2, \ldots, s_j$.)

Verified: no
Solve time: 2m03s

Solution

Let the first item selected by Algorithm C be the primary item $p$, and let its active options be ordered as $O_1,\ldots,O_k$. The hypothesis gives a distinct secondary item $s_j$ occurring as the final item of $O_j$.

The required modification is made only at the first branching on $p$. Introduce a variable $j_0$, local to the search at item $p$. When Algorithm C chooses $O_j$, set

$j_0\leftarrow j.$

During the subsequent recursive search, modify the treatment of the secondary items $s_1,\ldots,s_k$ as follows. When the algorithm reaches the step that would cover a secondary item $s_i$, perform the covering operation only when

$i\geq j_0.$

For $i<j_0$, leave $s_i$ in the active item list and do not cover it. All other primary and secondary items are processed exactly as in Algorithm C. When the search backtracks from the choice of $O_j$, restore the previous value of $j_0$ and undo the coverings in the usual reverse order.

The invariant is that, after choosing $O_j$, the only members of the set

${s_1,\ldots,s_k}$

that are removed from the residual problem are

$s_j,s_{j+1},\ldots,$

that have been reached and covered during later processing, while the members

$s_1,\ldots,s_{j-1}$

remain active. In particular, immediately after the choice of $O_j$, the items

${s_1,\ldots,s_{j-1}}$

are not covered by the chosen option. Thus the modified search has the stated behavior.

To prove that this reproduces the larger instance, replace each option $O_j$ by

$O'j=O_j\cup{s_1,\ldots,s{j-1}}.$

The item $s_i$ is then contained in every transformed option $O'j$ with $j\geq i$. If $O_j$ is selected, the transformed option covers $s_1,\ldots,s_j$, so the residual problem removes precisely the items that the modified algorithm treats as covered by the choice of $O_j$. The items $s_1,\ldots,s{j-1}$ require no further action because they have already been excluded from later consideration in the transformed instance, while the modified algorithm leaves their records unchanged and prevents them from being processed as newly covered secondary items.

Conversely, consider any solution produced by the modified algorithm. Let its selected option for $p$ be $O_j$. The modification only changes the handling of the secondary items in the displayed set, and all other coverings are identical to those in Algorithm C. Replacing $O_j$ by $O'j$ adds exactly the secondary items $s_1,\ldots,s{j-1}$ that the transformed instance requires. Since these items are distinct and are not used by any earlier transformed option in the same solution, the resulting set of transformed options covers exactly the same items as the original solution of the modified algorithm.

Therefore every solution of the modified algorithm corresponds to a solution of the expanded instance, and every solution of the expanded instance corresponds to a solution produced by the modified algorithm. The modification is therefore an exact simulation of the larger instance while avoiding the explicit addition of the items $s_1,\ldots,s_{j-1}$ to every option.

This completes the proof.

∎