Chapter XVII 3-Dimensional Matching

Two sides easy, three sides hard

Bipartite matching: O(V·E). 3-D matching: NP-complete. The third dimension is where the music ends.

3-Dimensional Matching takes three disjoint sets X, Y, Z each of size n and a family of triples drawn from them:

T \subseteq X \times Y \times Z, ∣ X ∣ = ∣ Y ∣ = ∣ Z ∣ = n . (1)

The question: does there exist a perfect tripartite matching — a subfamily of (1) that uses every element of every set exactly once?

M \subseteq T, ∣ M ∣ = n, every x, y, z appears in exactly one triple of M . (2)

Karp reduced 3-SAT to (2). The problem is interesting precisely because the bipartite (2-D) version is in P (Hopcroft-Karp, König's theorem) — adding a single dimension flips the complexity. 3-DM is NP-hard to approximate within a constant factor in the maximum-matching variant.

Figures, in plain terms

(1)

X × Y × Z is the Cartesian product of three sets: it's the collection of all triples (x, y, z) where x comes from X, y from Y, z from Z. Same multiplication symbol as in arithmetic, used for set products here.

For sets of size n each, X × Y × Z has n³ possible triples.

T ⊆ X × Y × Z picks a subset of those triples — the allowed combinations the problem hands you. Not every triple is necessarily compatible; T is the input to the problem.

|X| = |Y| = |Z| = n with the cardinality bars demands all three sets are equal size, n elements each.

(2)

M ⊆ T picks a subfamily of the allowed triples to be the matching.

|M| = n sizes the matching: exactly n triples chosen, the same as the size of each side.

The trailing condition is the matching property: every x, y, z appears in exactly one triple of M.

That "exactly one" is the strong condition. Compare bipartite matching (where each x has at most one partner): here we demand all three sides are perfectly matched at once. The third dimension makes this NP-complete, while two dimensions (Hopcroft–Karp) is polynomial.