3-Dimensional Matching

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.

Leave a Reply

Your email address will not be published.