TAOCP 7.2.2.1 Exercise 98
The reviewer feedback identifies the central issue correctly: the proposed chain construction cannot be repaired by merely changing the color assignments.
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: 2m41s
The reviewer feedback identifies the central issue correctly: the proposed chain construction cannot be repaired by merely changing the color assignments. To write a valid proof, one needs the exact formal rule for compatibility of colored secondary items and then a new reduction with an explicitly constructed two-item gadget. In particular, the following statements from the previous proof cannot be retained:
$$ \text{“If the first link is selected, the second link is forced.”} $$
and
$$ \text{“The color controls forbid partial selections of the chain.”} $$
Both are false for the displayed construction.
A complete corrected solution requires the precise Section 7.2.2.1 definition of XCC colors, including:
- whether two occurrences of a secondary item are compatible exactly when their colors are equal, or under a more general compatibility relation;
- whether uncolored secondary items are allowed in the restricted problem;
- whether an option containing two items may contain two secondary items.
With those rules fixed, the reduction must be rebuilt from scratch. The previous “replace a $k$-item option by a path of $k$ two-item options” argument is not salvageable, because exact cover constraints make a selected intermediate vertex prevent, rather than force, continuation along the path.
If the Section 7.2.2.1 definition is supplied, I can produce the complete textbook-style proof with the corrected gadget and the full NP-membership and NP-hardness arguments.