3-dimensional matching

In the case of 2-dimensional matching, the set T can be interpreted as the set of edges in a bipartite graph G = (X, Y, T); each edge in T connects a vertex in X to a vertex in Y.

Hence 3-dimensional matchings can be interpreted as a generalization of matchings to hypergraphs: the sets X, Y, and Z contain the vertices, each element of T is a hyperedge, and the set M consists of pairwise non-adjacent edges (edges that do not have a common vertex).

A 3-dimensional matching is a special case of a set packing: we can interpret each element (x, y, z) of T as a subset {x, y, z} of X ∪ Y ∪ Z; then a 3-dimensional matching M consists of pairwise disjoint subsets.

[1] It is NP-complete even in the special case that k = |X| = |Y| = |Z| and when each element is contained in at most 3 sets, i.e., when we want a perfect matching in a 3-regular hypergraph.

In computational complexity theory, this is also the name of the following optimization problem: given a set T, find a 3-dimensional matching M ⊆ T that maximizes |M|.

The hardness remains even when restricted to instances with exactly two occurrences of each element.

[13] There are various algorithms for 3-d matching in the massively parallel communication model.