Reduction: 3SAT → 3D Matching

Consider the following set of four triples, each represented by a triangular node joining a boy, girl, and pet:

The two boys $b_0, b_1$ and the two girls $g_0, g_1$ are not involved in any other triples. The any matching must contain either the two triples $(b_0, g_1, p_0), (b_1, g_0, p_2)$ or the two triples $(b_0, g_0, p_1), (b_1, g_1, p_3)$. Therefore the “gadget” has two possible states.

So therefore if we want to transform an instance of 3SAT to one of 3D MATCHING, we start by creating a copy of the gadget for each variable $x$. Call the resulting nodes $p_{x_1}, b_{x_0}, g_{x_1}$ and so on, the intended interpretation is boy $b_{x0}$ is matched with girl $g_{x1}$ if $x = true$, and with girl $g_{x0}$ if $x = false$

Then we create triples that mimic clauses, for each clause (say $c = (x \vee \bar{y} \vee z)$, introduce a new boy $b_c$ and a new girl $g_c$, they will be involved in three triples, one for each literal in the clause, and the pets in three triples must reflect the three ways where the clause can be satisfied

1. $x = true$
   1. Have triple $(b_c, g_c, p_{x1})$
   2. If $p_{x1}$ is taken, then the possible assignment of the gadget representing $x$ is only TRUE
   3. If $x$ is false, then $p_{x1}, p_{x3}$ is taken, and $g_c$ and $b_c$ cannot be accommodated with this triplet

2. $y = false$

3. $z = true$

We need to make sure that every occurrence of a literal in a clause $c$ there is a different pet to match with $b_c$ and $g_c$.

By an earlier reduction we can assume that no literal appears more than twice, so each variable gadget has enough pets, two for negated occurrences and two for unnegated.

Complete?

• For any matching we can recover a satisfying truth assignment by looking at each variable gadget

• For each clause the pet the corresponds to one of its satisfying literals

One last problem remained:

• In the matching defined at the end, some pets may be left unmatched.

• Exactly $2n-m$ pets.

• Easy to fix: Add $2n-m$ new boy-girl couples that are “generic animal-lovers”