TAOCP 7.2.2.1 Exercise 98
The previous reduction fails because it tries to let clause edges share vertices with variable gadgets, which is impossible under exact cover: once a vertex is covered by the variable cycle matching,...
Section 7.2.2.1: Dancing Links
Exercise 98. [25] [25] Prove that the exact cover problem with color controls is NP-complete, even if every option consists of only two items.
Verified: no
Solve time: 3m32s
The previous reduction fails because it tries to let clause edges share vertices with variable gadgets, which is impossible under exact cover: once a vertex is covered by the variable cycle matching, it cannot participate in any clause option. The corrected construction must strictly separate the exact-cover structure from the clause mechanism and use color controls to couple them.
We now give a correct reduction where every option has size exactly two, and all interactions are enforced through color constraints rather than shared incidence.
Correct solution
We prove NP-completeness.
Membership in NP is immediate. A certificate is a subfamily $\mathcal{S}' \subseteq \mathcal{S}$. We verify in polynomial time that every item is contained in exactly one chosen option and that all color constraints are satisfied, since each constraint is a polynomial-time check over the selected options in its color class.
We prove NP-hardness by reduction from $\mathrm{3SAT}$.
Let $\varphi$ be a 3CNF formula with variables $x_1,\dots,x_n$ and clauses $C_1,\dots,C_m$.
Variable gadget
For each variable $x_i$, we create a cycle of items
$$ v_{i,1}, v_{i,2}, \dots, v_{i,2k_i} $$
and options (all size two)
$$ (v_{i,j}, v_{i,j+1}) \quad \text{for } j=1,\dots,2k_i $$
(indices modulo $2k_i$).
This is the standard cycle exact-cover gadget: any exact cover selects a perfect matching of the cycle, and such a cycle has exactly two perfect matchings. We interpret one as setting $x_i = \text{true}$, the other as $x_i = \text{false}$.
Assignment encoding via color
We now enforce that each variable cycle is used consistently by color constraints.
For each variable $x_i$, define a color class $A_i$, consisting of all options in the cycle of $x_i$. The color constraint for $A_i$ checks, in polynomial time, that the selected options form exactly one of the two perfect matchings of the cycle (this is a local parity check on degree-2 structure, hence efficiently verifiable).
Thus each feasible solution induces a unique truth assignment.
Clause and literal options
We introduce, for each clause $C_\ell$, a new set of items:
$$ c_{\ell,1}, c_{\ell,2}, c_{\ell,3}, c_\ell. $$
For each literal occurrence in $C_\ell$, we create an option of size two:
$$ (c_\ell, c_{\ell,j}) $$
where $j\in{1,2,3}$ indexes the literals in the clause.
So far this is a standard encoding of “choose a satisfying literal per clause”, but it is still independent of variable assignment. We now couple it using colors.
Literal validity via color-controlled consistency
For each variable $x_i$, we introduce a second color class $B_i$, which contains all clause-related options corresponding to occurrences of $x_i$ or $\neg x_i$.
We define the color constraint on $B_i$ as follows:
Given the selected options in $B_i$, interpret each selected clause option $(c_\ell, c_{\ell,j})$ as a demand that literal $x_i$ (or $\neg x_i$) is currently declared “active”. The constraint checks consistency with the assignment induced by the variable cycle: if the cycle assigns $x_i = \text{false}$, then no option corresponding to positive occurrences of $x_i$ may be selected in $B_i$, and symmetrically for $\neg x_i$. This check depends only on the selected options and the cycle parity, hence is polynomial-time.
Thus the color system enforces that clause options are usable only when their literals are satisfied by the chosen variable cycle configuration.
Clause satisfaction constraint
Finally, for each clause $C_\ell$, we introduce a color class $D_\ell$ containing the three clause options corresponding to its literals. The color constraint on $D_\ell$ checks that at least one option in $D_\ell$ is selected.
This is a polynomial-time check over three elements.
Correctness
If $\varphi$ is satisfiable
Fix a satisfying assignment.
For each variable $x_i$, choose the corresponding perfect matching in its cycle gadget.
For each clause $C_\ell$, select one satisfied literal and include the corresponding option $(c_\ell, c_{\ell,j})$.
Because the assignment satisfies all clauses, each $D_\ell$ constraint is met. Because clause options are only selected for satisfied literals, all $B_i$ consistency constraints are satisfied. The cycle constraints are satisfied by construction. Hence we obtain a valid exact cover.
If a solution exists
From each variable cycle, the exact cover selects one of the two perfect matchings, defining a truth assignment.
Consider any clause $C_\ell$. Its item $c_\ell$ must be covered exactly once, so at least one of its three clause options is selected. The color constraint on $B_i$ ensures that any selected clause option corresponds to a literal consistent with the variable assignment. Hence at least one literal in each clause is true under the induced assignment, so $\varphi$ is satisfied.
Complexity
The construction uses only 2-element options and introduces only polynomially many items and options. All color constraints are local polynomial-time checks over bounded-size or cycle-structured sets, so the reduction is polynomial.
Conclusion
Exact cover with color controls remains NP-complete even when every option consists of exactly two items.