3-dimensional matching
Encyclopedia
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, a 3-dimensional matching is a generalization of bipartite matching (a.k.a. 2-dimensional matching) to 3-uniform hypergraph
Hypergraph
In mathematics, a hypergraph is a generalization of a graph, where an edge can connect any number of vertices. Formally, a hypergraph H is a pair H = where X is a set of elements, called nodes or vertices, and E is a set of non-empty subsets of X called hyperedges or links...
s. Finding a largest 3-dimensional matching is a well-known NP-hard
NP-hard
NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...
problem in computational complexity theory
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
.
Definition
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 (x, y, z) 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 (x1, y1, z1) ∈ M and (x2, y2, z2) ∈ 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 (a) shows the set T (gray areas). Figure (b) shows a 3-dimensional matching M with |M| = 2, and Figure (c) shows a 3-dimensional matching M with |M| = 3.The matching M illustrated in Figure (c) is a maximum 3-dimensional matching, i.e., it maximises |M|. The matching illustrated in Figures (b)–(c) are maximal 3-dimensional matchings, i.e., they cannot be extended by adding more elements from T.
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 (x1, y1) ∈ M and (x2, y2) ∈ 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 graph
Bipartite graph
In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
G = (X, Y, T); 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 of T is a hyperedge, and the set M consists of pairwise non-adjacent edges (edges that do not have a common vertex).
Comparison with set packing
A 3-dimensional matching is a special case of a set packingSet packing
Set packing is a classical NP-complete problem in computational complexity theory and combinatorics, and was one of Karp's 21 NP-complete problems.Suppose we have a finite set S and a list of subsets of S...
: 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.
Decision problem
In computational complexity theory, 3-dimensional matching is also the name of the following decision problemDecision problem
In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is a 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
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
; it is one of Karp's 21 NP-complete problems
Karp's 21 NP-complete problems
One of the most important results in computational complexity theory was Stephen Cook's 1971 demonstration of the first NP-complete problem, the boolean satisfiability problem...
.
The problem is NP-complete even in the special case that k = |X| = |Y| = |Z|. In this case, a 3-dominating 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 problemOptimization problem
In mathematics and computer science, an optimization problem is the problem of finding the best solution from all feasible solutions. Optimization problems can be divided into two categories depending on whether the variables are continuous or discrete. An optimization problem with discrete...
: 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
NP-hard
NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...
, 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 (maximum 2-dimensional matching), for example, the Hopcroft–Karp algorithm.
Approximation algorithms
The problem is APX-complete, that is, it is hard to approximateApproximation algorithm
In computer science and operations research, approximation algorithms are algorithms used to find approximate solutions to optimization problems. Approximation algorithms are often associated with NP-hard problems; since it is unlikely that there can ever be efficient polynomial time exact...
within some constant. On the positive side, for any constant ε > 0 there is a polynomial-time (3/2 + ε)-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.