Let X, Y, and Z be finite, disjoint sets, and let T be a subset of X × Y × Z. That is, T consists of triples such that x ∈ X, y ∈ Y, and z ∈ Z. Now M ⊆ T is a 3-dimensional matching if the following holds: for any two distinct triples ∈ M and ∈ M, we have x1 ≠ x2, y1 ≠ y2, and z1 ≠ z2.
Example
The figure on the right illustrates 3-dimensional matchings. The set X is marked with red dots, Y is marked with blue dots, and Z is marked with green dots. Figure shows the set T. Figure shows a 3-dimensional matching M with |M| = 2, and Figure shows a 3-dimensional matching M with |M| = 3. The matching M illustrated in Figure is a maximum 3-dimensional matching, i.e., it maximises |M|. The matching illustrated in Figures – are maximal 3-dimensional matchings, i.e., they cannot be extended by adding more elements from T. Here is example interactive visualisation in
Comparison with bipartite matching
A 2-dimensional matching can be defined in a completely analogous manner. Let X and Y be finite, disjoint sets, and let T be a subset of X × Y. Now M ⊆ T is a 2-dimensional matching if the following holds: for any two distinct pairs ∈ M and ∈ M, we have x1 ≠ x2 and y1 ≠ y2. In the case of 2-dimensional matching, the set T can be interpreted as the set of edges in a bipartite graphG = ; each edge in T connects a vertex in X to a vertex in Y. A 2-dimensional matching is then a matching in the graph G, that is, a set of pairwise non-adjacent edges. 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 ofT is a hyperedge, and the set M consists of pairwise non-adjacent edges. In case of 2-dimensional matching, we have Y = Z.
A 3-dimensional matching is a special case of a set packing: we can interpret each element of T as a subset of X ∪ Y ∪ Z; then a 3-dimensional matching M consists of pairwise disjoint subsets.
Decision problem
In computational complexity theory, 3-dimensional matching is also the name of the following decision problem: given a set T and an integer k, decide whether there exists a 3-dimensional matching M ⊆ T with |M| ≥ k. This decision problem is known to be NP-complete; it is one of Karp's 21 NP-complete problems. There exist though polynomial time algorithms for that problem for dense hypergraphs. The problem is NP-complete even in the special case that k = |X| = |Y| = |Z|. In this case, a 3-dimensional matching is not only a set packing but also an exact cover: the set M covers each element of X, Y, and Z exactly once.
Optimization problem
A maximum 3-dimensional matching is a largest 3-dimensional matching. 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|. Since the decision problem described above is NP-complete, this optimization problem is NP-hard, and hence it seems that there is no polynomial-time algorithm for finding a maximum 3-dimensional matching. However, there are efficient polynomial-time algorithms for finding a maximum bipartite matching, for example, the Hopcroft–Karp algorithm.
Approximation algorithms
The problem is APX-complete, that is, it is hard to approximate within some constant. However, for any constant ε > 0 there is a polynomial-time -approximation algorithm for 3-dimensional matching. There is a very simple polynomial-time 3-approximation algorithm for 3-dimensional matching: find any maximal 3-dimensional matching. Just like a maximal matching is within factor 2 of a maximum matching, a maximal 3-dimensional matching is within factor 3 of a maximum 3-dimensional matching.
