Exact cover

[gareth_rees]

Karp (1972) introduces the name ‘exact cover’ for the following decision problem:

INPUT: Family S_j of subsets of a set u_i, i=1,2,…,t

PROPERTY: There is a subfamily T_h ⊆ S_j such that the sets T_h are disjoint and ∪T_h = ∪S_j = u_i, i=1,2,…,t

(The problem being to determine, for an arbitrary input, whether it possesses the property.) Karp goes on to prove that this problem is NP-complete, using a reduction from chromatic number, which has a reduction from satisfiability with at most three literals per clause, which in turn has a reduction from satisfiability, which he proves is NP-complete directly.

( Instances of this problem often arise in the solution of combinatorial problems … )