### Exact cover

Dec. 14th, 2015 06:34 pm**gareth_rees**

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

INPUT: Family

S_{j}of subsets of a setu_{i},i=1,2,…,t

PROPERTY: There is a subfamilyT_{h}⊆S_{j}such that the setsT_{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 … )**