Let be sets, and consider . is a 3-dimensional matching if for all , , , and . The language for the decision problem is as follows
NP-Complete
Info
is NP-complete
We can check if a subset of is a 3-dimensional matching by looking for conflicts in polynomial time. Thus .
To show completeness, we reduce from 3SAT. Given a Boolean formula with variables . For each variable, construct a “rose” gadget as below with petals. The even petals represent a true assignment, while the odd petals represent a false assignment.
For each clause , create two additional nodes, and attach it to the outer nodes of the respective true / false petals for each . Let , so any 3-dimensional matching corresponds to picking a parity for the false literal in the rose gadget, and matching each clause gadget with the unused petal nodes. This gives a satisfying assignment to , so is NP-complete.
