Last one for today. I’m not sure how exactly I’ll space these out. We’ll see.
The Problem: 3-Dimensional Matching (3DM)
The Definition: Given disjoint sets W,X,Y all with the same number (q) of elements, and a set M of triples from WxXxY. Is there a subset M’ of M of size q where no two elements of M’ agree in any coordinate?
I always have trouble picturing what this means, so here’s an example:
Let W = {1,2,3,4}, X = {10,20,30,40}, Y = {100,200,300,400}. q is 4 in this case.
M is a set of triples like (1,30,400), (2,20,100), and so on, with one element from each of W,X, and Y.
We’re asking for q elements of M that have no duplicates in any coordinate. In other words, each of {1,2,3,4} appears in exactly one element of M’, each of {10,20,30,40} appears in exactly one element of M’, and so on. So, a legal M’ could be:
{(1,20,300), (2,30,400), (3,40,100), (4,10,200)}
..assuming all 4 of those triples happened to be in the M we were given.
The Reduction: From 3SAT. Pages 50-52 explain how we take the clauses and build W, X, Y, and M from them. It’s pretty crazy-M contains 3 kinds of triples for 3 different kinds of jobs, build according to 3 different sets of rules.
Difficulty: 8. I couldn’t imagine a student coming up with this without a lot of hand-holding.