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: yes
Solve time: 1m45s

Solution

Let the columns of $A$ correspond to the item set $U$, and let the rows of $A$ be the options of the original exact cover problem. Construct $A'$ by adding one new item $z$ and two new rows. The first new row, denoted $C$, contains only $z$. The second new row, denoted $S$, contains $z$ together with every item in $U$. The original rows are left unchanged.

In matrix form, if $A$ has $M$ rows and $N$ columns, then $A'$ has $M+2$ rows and $N+1$ columns. The first $M$ rows of $A'$ are obtained from $A$ by appending a zero in the new column. The row $C$ has a one only in the new column, and the row $S$ has ones in every column. Thus

$$ A'= \begin{pmatrix} A&0\ 0\ \cdots\ 0&1\ 1\ \cdots\ 1&1 \end{pmatrix}. $$

Let $\mathcal S(A)$ denote the set of exact covers of $A$. We prove that the exact covers of $A'$ are precisely

$$ {X\cup{C}:X\in\mathcal S(A)}\cup{{S}}. $$

First consider any $X\in\mathcal S(A)$. The rows in $X$ cover every item in $U$ exactly once. Since the original rows have a zero in the new column, they cover $z$ zero times. Adding the row $C$ gives one occurrence of $z$ and does not affect the coverage of any item in $U$. Therefore $X\cup{C}$ is an exact cover of $A'$.

The row $S$ contains every item of $U$ and also contains $z$. Hence the single row set ${S}$ covers every item of $A'$ exactly once, so ${S}$ is an exact cover of $A'$.

It remains to show that no other exact covers exist. Let $Y$ be an exact cover of $A'$. The new item $z$ must be covered exactly once. The only rows containing $z$ are $C$ and $S$.

Suppose first that $S\in Y$. Since $S$ already covers every item in $U$ and also covers $z$, no other row can belong to $Y$, because any additional row would make some item occur more than once. Therefore

$$ Y={S}. $$

Suppose instead that $S\notin Y$. Then $z$ must be covered by $C$, so

$$ C\in Y. $$

The row $C$ contains no item of $U$, so the remaining rows $Y-{C}$ must cover the items of $U$ exactly once. These remaining rows are all original rows of $A$, and their incidence with $U$ is unchanged from $A$. Hence $Y-{C}$ is an exact cover of $A$, which gives

$$ Y=X\cup{C} $$

for some $X\in\mathcal S(A)$.

Therefore every exact cover of $A'$ is either ${S}$ or is obtained uniquely from an exact cover of $A$ by adjoining $C$. The first type contributes one solution, and the second type contributes exactly as many solutions as $A$ has. Consequently,

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

The construction adds exactly one solution while preserving all existing solutions in one-to-one correspondence, so the required exact cover problem $A'$ has exactly one more solution than $A$.

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

This completes the proof.

∎