Tag Archives: Difficulty 3

This is not one of the “core six”, but it is used a lot in reductions, so it’s worth including since it builds right off of 3DM

Also, I think I will include examples for lots of these problems.  Lots of times I have trouble parsing the problem description, so creating a concrete example is helpful.

The problem: Exact Cover by 3-Sets (X3C)

The definition: Given a set X, with |X| = 3q (so, the size of X is a multiple of 3), and a collection C of 3-element subsets of X.  Can we find a subset C’ of C where every element of X occurs in exactly one member of C’?  (So, C’ is an “exact cover” of X).

Example:  Suppose X was {1,2,3,4,5,6}

If C was {{1,2,3},{2,3,4},{1,2,5},{2,5,6}, {1,5,6}}  then we could choose C’ to be {{2,3,4},{1,5,6}} as an exact cover because each element in X appears exactly once.

If instead, C was {{1,2,3},{2,4,5},{2,5,6}}, then any C’ we choose will not be an exact cover (we need all 3 subsets to cover all elements in X at least once, but then the element 2 appears three times).

Note that if we do have an exact cover, C’ will contain exactly q elements.

The proof:G&J prove this “by restriction” which basically means that they show how X3C is a more general version of 3DM .  If you view an instance of 3DM as a special case of X3C by letting X_X3C = W∪X_3DM∪Y and C = all q³ triples taking one element from W, one element from X_3DM, and one element from Y), then the C’ you get as a solution to X3C is also a matching for 3DM.

(Note that lots of these reductions will be between problems that use the same symbols in both problems.  I’ll do my best to disambiguate by using subscripts to mark where the common letter comes from.  So, in this case X_3DM is the set X that we get from the 3DM problem (one of the 3 input sets), and X_X3C is the set we build for the X3C problem (the set we need to cover).  Hopefully that doesn’t make things more confusing)

(Also note that like many (most?) Computer Science people, I’m a big fan of nested parentheses.  I’m sure all of you can follow along with that. (Right?))

Personally, I don’t like proofs by restriction as a way to teach this stuff to students.  It’s very easy to mess up the “this is a special case” argument- you get incorrect arguments like “this is just a special case of SAT where we return true wherever there’s a cover and false when we don’t!”.  Also it feels like you’re going backwards from a real reduction, and since getting the direction wrong is probably the #1 most common issue students have in doing reductions, anything that makes their job harder isn’t a great idea.

If I taught this in a class, I’d make them do a proper reduction out of it- start with an instance of 3DM (W, X_3DM, and Y), and build an instance of X3C (creating X_X3C and C), and going from there.

Difficulty: 3.  It’s only not a 2 because I, at least, have trouble understanding what the X3C and 3DM problems are asking.  It’s not as straightforward to explain as many other problems