NP Complete, Exact Cover

Exact Cover

Given a collection of subsets of a set U, does some subcollection of these subsets form a partition of U?

If we are building U and its subsets from scratch, it's easy to construct a collection of j subsets that are either in or out.  Place a unique element in each set, such as e1 through ej, and create another dummy set that contains e1 through ej.  The designated collection of j sets is in iff the dummy set is out.

Given an instance of 3-sat, focus on one of the boolean variables x.  Create a set for each literal x in the boolean expression.  These sets establish a true value of x, wherever it appears.  Using the technique described above, build a dummy set xf, for "x is false".  Either xf is in our partition, or all the sets associated with the instances of x are brought in.  In other words, x is false or x is true.

Build another suite of sets, one for each literal x, indicating that that instance of x is false.  Build a dummy set xt, for "x is true", such that the sets that make each x false are brought in iff xt is out.

Finally add a common element to xf and xt, so that exactly one of these sets participates in the cover of U.  Now each literal x is set to true or false, consistently, across the boolean expression.

Consider a clause that contains x, such as x|y|z.  There are 7 combinations that satisfy this clause.  Create 7 sets to represent these combinations.  The seven sets s1 through s7 share a common element, so that exactly one is brought in.

This clause introduces 6 new elements c1 c2 c3 d1 d2 d3.  These elements determine whether the first, second, or third atoms in the clause are satisfied by the boolean variables.  Each of the seven sets s1 through s7 contains c1 or d1, c2 or d2, and c3 or d3.  After all, each atom is going to be satisfied, or it is not.  To illustrate, let s1 be the set that asserts all three atoms are true.  Thus s1 contains c1 c2 and c3.  Now the set that makes this instance of x true, as the boolean variables are mapped out, contains d1.  Similarly, "y true" includes d2, and "z true" includes d3.  Note that "x false" includes c1, and would not be compatible with s1, though it might be compatible with s4.  An exact cover selects one of s1 through s7, which forces certain atoms to be satisfied, which must agree with the boolean variables as they are assigned.

Repeat this process for each clause.  Put this all together and U has a partition iff 3-sat has a solution.  Exact cover is np complete.

If you think about it, there is no need for the common element among s1 through s7.  The assignment of true or false to the three literals brings in some of c1 through c3 and/or d1 through d3.  We need to pull in the complement, and only one of the 7 sets will accomplish this.

There are 7 sets per clause, plus two sets per literal, plus two sets per variable.  A partition requires one set per variable (true or false), one set per literal, and one set per clause.  The number of sets that create the partition is prescribed.