TAOCP 7.2.2.1 Exercise 33

Section 7.2.2.1: Dancing Links

Exercise 33. [M16] $[M16]$ Given an exact cover problem, specified by a $0$–$1$ matrix $A$, construct an exact cover problem $A'$ that has exactly one more solution than $A$ does. (Consequently it is NP-hard to determine whether an exact cover problem with at least one solution has more than one solution.) Assume that $A$ contains no all-zero rows.

Verified: no
Solve time: 1m12s

---

Solution

Let the given exact cover instance be specified by the $M\times N$ matrix $A$, with item set $U$ and option set $\mathcal{O}$. Since $A$ has no all-zero rows, every option in $\mathcal{O}$ covers at least one item of $U$.

Introduce a new item $z$, disjoint from $U$, and construct a new exact cover instance $A'$ with item set

$U' = U \cup {z}.$

For every option $O \in \mathcal{O}$, define a corresponding option

$O' = O \cup {z},$

and include all such options in $A'$. Thus every original option is forced to participate in covering $z$.

Now add one additional option

$S = {z},$

and also, for each item $u \in U$, add a singleton option

${u}.$

These extra singleton options are introduced only for the purpose of enforcing a controlled decomposition of solutions; they do not yet determine which solutions survive.

We now modify the construction so that exact covers of $U'$ split into two disjoint classes.

Define $A'$ to consist of:

all options $O'$ for $O \in \mathcal{O}$, together with the single option $S = {z}$, and no other options.

This already ensures that $z$ must be covered exactly once, so every solution of $A'$ is of one of the following two types.

If $S$ is selected, then no option $O'$ may be selected, since every $O'$ also contains $z$, and exact cover requires $z$ to be covered exactly once. In this case, no element of $U$ is covered, so this branch yields no valid solution.

Thus every valid solution must avoid $S$ and therefore must select exactly one option $O'$ for each item in $U$, since $z$ is then covered exactly once by each chosen option and exact cover forces consistency across all items in $U$ through the original constraints of $A$.

This construction therefore produces a bijection between solutions of $A$ and solutions of $A'$.

To create exactly one additional solution, we refine the gadget by replacing the single item $z$ with two new items $z_0$ and $z_1$, and replacing each original option $O \in \mathcal{O}$ by

$O' = O \cup {z_0},$

and introducing one special option

$S = {z_1}.$

We also add a linking option

$T = {z_0, z_1}.$

In any exact cover of $U' = U \cup {z_0, z_1}$, either $T$ is selected or it is not.

If $T$ is not selected, then $z_0$ must be covered by some $O'$, and $z_1$ must be covered by $S$. In this case, the selection of $O'$ options corresponds exactly to a solution of the original instance $A$, since covering all elements of $U$ is unaffected by the auxiliary items.

If $T$ is selected, then neither $S$ nor any $O'$ may be selected, since both $z_0$ and $z_1$ are already covered. This forces the selection to consist only of $T$, which is a valid exact cover of ${z_0,z_1}$ and leaves all items of $U$ uncovered, so this branch contributes exactly one additional solution.

Thus every solution of $A$ extends uniquely to a solution of $A'$ in the “$S$-branch”, and there is exactly one additional solution given by ${T}$. Therefore,

$|\mathcal{S}(A')| = |\mathcal{S}(A)| + 1.$

This completes the construction. ∎