Exact Cover by 3-Sets

Input

Set $X$ with $|X| = 3q$, collection $C$ of 3-element subsets of $X$.

Question

Does $C$ contain an exact cover for $X$, i.e. a subcollection $C' \subseteq C$ such that every element of $X$ occurs in exactly one member of $C'$?

Classes

• NP-complete

Comments

Remains NP-complete if no element occurs in more than three subsets, but is solvable in polynomial time if no element occurs in more than two subsets (Garey & Johnson, 1979). Related [problem:exact-cover-by-2-sets] problem is also solvable in polynomial time by matching techniques.

Proofs

NP-complete

Transformation from 3-Dimensional Matching (Karp, 1972).

Reducible from

• 3-Dimensional Matching

Reducible to

• Bounded Diameter Spanning Tree
• Minimum Cover
• Set Packing

References

• Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co.
• Karp, R. M. (1972). Reducibility among Combinatorial Problems. In Complexity of Computer Computations (pp. 85–103). Springer US. https://doi.org/10.1007/978-1-4684-2001-2_9