Log in

Exact cover - Gareth Rees


Previous Entry Share Next Entry
Exact cover

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

INPUT: Family Sj of subsets of a set ui, i=1,2,…,t

PROPERTY: There is a subfamily ThSj such that the sets Th are disjoint and ∪Th = ∪Sj = ui, 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 … )

garethrees.org Powered by LiveJournal.com