3-Dimensional Matching

Input

Set $M \subseteq W \times X \times Y$, where $W$, $X$ and $Y$ are disjoint sets having the same number $q$ of elements.

Question

Does $M$ contain a matching, i.e. a subset $M' \subseteq M$ such that $|M'| = q$ and no two elements of $M'$ agree in any coordinate?

Classes

• NP-complete

Comments

Remains NP-complete if $M$ is pairwise consistent, i.e. if for all elements $a$, $b$, $c$, whenever there exist elements $w$, $z$, and $y$ such that $(a, b, w) \in M$, $(a, x, c) \in M$, and $(y, b, c) \in M$, then $(a, b, c) \in M$. Also remains NP-complete if no element occurs in more than three triples, but is solvable in polynomial time if no element occurs in more than two triples (Garey & Johnson, 1979). The related [problem:2-dimensional-matching] problem (where $M \subseteq W \times X$) is also solvable in polynomial time (Lawler, 1976).

Proofs

NP-complete

Transformation from 3-Satisfiability (Karp, 1972).

Reducible from

• 3-Satisfiability

Reducible to

• Bin Packing
• Exact Cover by 3-Sets
• Partition into Isomorphic Subgraphs
• Partition into Triangles
• Partition

References

• Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co.
• Lawler, E. L. (1976). Combinatorial optimization: networks and matroids. Holt, Rinehart.
• Karp, R. M. (1972). Reducibility among Combinatorial Problems. In Complexity of Computer Computations (pp. 85–103). Springer US. https://doi.org/10.1007/978-1-4684-2001-2_9