TAOCP 7.2.2.1 Exercise 224
Let the items be $x_1, x_2, \dots, x_n$.
Section 7.2.2.1: Dancing Links
Exercise 224. ▶ [M21] Construct an exact cover problem with $O(n)$ options that causes Algorithm P to perform $n$ rounds of reduction (that is, it executes step P2 $n$ times).
Verified: yes
Solve time: 1m51s
Solution
Let the items be $x_1, x_2, \dots, x_n$. Define an exact cover instance in which the set of options consists of the $n$ singleton options
$$ O_i = {x_i}, \qquad 1 \le i \le n. $$
Each item $x_i$ occurs in exactly one option, so the initial active data structure has
$$ \mathrm{LEN}(x_i) = 1 \qquad \text{for all } i. $$
In step P2 of Algorithm P, the algorithm selects an item $i$ among those that still need to be covered. Since every item has exactly one active option, each selected item satisfies the condition that exactly one option involves it, so no branching occurs at any stage.
Suppose the algorithm selects any item $x_k$ at the first execution of P2. The only option involving $x_k$ is $O_k = {x_k}$. Covering $x_k$ deletes $O_k$ and removes $x_k$ from the set of uncovered items. No other option is affected because no other option contains $x_k$.
After this operation, the residual instance is identical in form to the original one but with one fewer item, namely the set
$$ {x_1, \dots, x_{k-1}, x_{k+1}, \dots, x_n}, $$
and exactly one option per remaining item.
The same argument applies inductively. After $t$ executions of P2, exactly $t$ items have been removed, and the residual instance still consists solely of singleton options corresponding to the remaining items. At each stage every remaining item again has exactly one active option, so step P2 is executed once more.
This process continues until all $n$ items have been removed, at which point step P2 is executed exactly $n$ times.
The number of options in the construction is exactly $n$, so it is $O(n)$.
No instance with fewer than $n$ items can force more than $n$ executions of P2, since each execution removes at least one item and items are never reintroduced during the algorithm.
Thus this construction achieves $n$ rounds of reduction with $O(n)$ options.
This completes the proof. ∎