3-dimensional matching

Last updated
3-dimensional matchings. (a) Input T. (b)-(c) Solutions. 3-dimensional-matching.svg
3-dimensional matchings. (a) Input T. (b)–(c) Solutions.

In the mathematical discipline of graph theory, a 3-dimensional matching is a generalization of bipartite matching (also known as 2-dimensional matching) to 3-partite hypergraphs, which consist of hyperedges each of which contains 3 vertices (instead of edges containing 2 vertices in a usual graph).

Contents

3-dimensional matching, often abbreviated as 3DM, is also the name of a well-known computational problem: finding a largest 3-dimensional matching in a given hypergraph. 3DM is one of the first problems that were proved to be NP-hard.

Definition

Let X, Y, and Z be finite 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.

Here is example interactive visualisation in javascript

Comparison with bipartite matching

A 2-dimensional matching can be defined in a completely analogous manner. Let X and Y be finite 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 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). In case of 2-dimensional matching, we have Y = Z.

Comparison with set packing

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.

Decision problem

In computational complexity theory, 3-dimensional matching (3DM) is 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. [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. [1] [2] [3] 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. [4] The proof is by reduction from 3SAT. Given a 3SAT instance, we construct a 3DM instance as follows: [2] [5]

Special cases

There exist polynomial time algorithms for solving 3DM in dense hypergraphs. [6] [7]

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 (maximum 2-dimensional matching), for example, the Hopcroft–Karp algorithm.

Approximation algorithms

There is a very simple polynomial-time 3-approximation algorithm for 3-dimensional matching: find any maximal 3-dimensional matching. [8] Just like a maximal matching is within factor 2 of a maximum matching, [9] a maximal 3-dimensional matching is within factor 3 of a maximum 3-dimensional matching.

For any constant ε > 0 there is a polynomial-time (4/3 + ε)-approximation algorithm for 3-dimensional matching. [10]

However, attaining better approximation factors is probably hard: the problem is APX-complete, that is, it is hard to approximate within some constant. [11] [12] [8]

It is NP-hard to achieve an approximation factor of 95/94 for maximum 3-d matching, and an approximation factor of 48/47 for maximum 4-d matching. The hardness remains even when restricted to instances with exactly two occurrences of each element. [13]

Parallel algorithms

There are various algorithms for 3-d matching in the Massively parallel computation model. [14]

See also

Notes

  1. 1 2 Karp (1972).
  2. 1 2 Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness . Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN   9780716710455. MR   0519066. OCLC   247570676., Section 3.1 and problem SP1 in Appendix A.3.1.
  3. ↑ Korte, Bernhard; Vygen, Jens (2006), Combinatorial Optimization: Theory and Algorithms (3rd ed.), Springer , Section 15.5.
  4. ↑ Papadimitriou & Steiglitz (1998), Section 15.7.
  5. ↑ Demaine, Erik (2016). "16. Complexity: P, NP, NP-completeness, Reductions". YouTube .
  6. ↑ Karpinski, Rucinski & Szymanska (2009)
  7. ↑ Keevash, Knox & Mycroft (2013)
  8. 1 2 Kann (1991)
  9. ↑ Matching (graph theory)#Properties.
  10. ↑ Cygan, Marek (2013). "Improved Approximation for 3-Dimensional Matching via Bounded Pathwidth Local Search". 2013 IEEE 54th Annual Symposium on Foundations of Computer Science. pp. 509–518. arXiv: 1304.1424 . Bibcode:2013arXiv1304.1424C. doi:10.1109/FOCS.2013.61. ISBN   978-0-7695-5135-7. S2CID   14160646.
  11. ↑ Crescenzi et al. (2000).
  12. ↑ Ausiello et al. (2003), problem SP1 in Appendix B.
  13. ↑ Chlebík, Miroslav; Chlebíková, Janka (2006-04-04). "Complexity of approximating bounded variants of optimization problems". Theoretical Computer Science. Foundations of Computation Theory (FCT 2003). 354 (3): 320–338. doi: 10.1016/j.tcs.2005.11.029 . ISSN   0304-3975.
  14. ↑ Hanguir, Oussama; Stein, Clifford (2020-09-21). "Distributed Algorithms for Matching in Hypergraphs". arXiv: 2009.09605 [cs.DS].

Related Research Articles

In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) is the problem of determining if there exists an interpretation that satisfies a given Boolean formula. In other words, it asks whether the variables of a given Boolean formula can be consistently replaced by the values TRUE or FALSE in such a way that the formula evaluates to TRUE. If this is the case, the formula is called satisfiable. On the other hand, if no such assignment exists, the function expressed by the formula is FALSE for all possible variable assignments and the formula is unsatisfiable. For example, the formula "a AND NOT b" is satisfiable because one can find the values a = TRUE and b = FALSE, which make (a AND NOT b) = TRUE. In contrast, "a AND NOT a" is unsatisfiable.

The subset sum problem (SSP) is a decision problem in computer science. In its most general formulation, there is a multiset of integers and a target-sum , and the question is to decide whether any subset of the integers sum to precisely . The problem is known to be NP-complete. Moreover, some restricted variants of it are NP-complete too, for example:

<span class="mw-page-title-main">Clique problem</span> Task of computing complete subgraphs

In computer science, the clique problem is the computational problem of finding cliques in a graph. It has several different formulations depending on which cliques, and what information about the cliques, should be found. Common formulations of the clique problem include finding a maximum clique, finding a maximum weight clique in a weighted graph, listing all maximal cliques, and solving the decision problem of testing whether a graph contains a clique larger than a given size.

<span class="mw-page-title-main">Combinatorial optimization</span> Subfield of mathematical optimization

Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combinatorial optimization problems are the travelling salesman problem ("TSP"), the minimum spanning tree problem ("MST"), and the knapsack problem. In many such problems, such as the ones previously mentioned, exhaustive search is not tractable, and so specialized algorithms that quickly rule out large parts of the search space or approximation algorithms must be resorted to instead.

<span class="mw-page-title-main">Independent set (graph theory)</span> Unrelated vertices in graphs

In graph theory, an independent set, stable set, coclique or anticlique is a set of vertices in a graph, no two of which are adjacent. That is, it is a set of vertices such that for every two vertices in , there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in . A set is independent if and only if it is a clique in the graph's complement. The size of an independent set is the number of vertices it contains. Independent sets have also been called "internally stable sets", of which "stable set" is a shortening.

<span class="mw-page-title-main">Vertex cover</span> Subset of a graphs vertices, including at least one endpoint of every edge

In graph theory, a vertex cover of a graph is a set of vertices that includes at least one endpoint of every edge of the graph.

In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems with provable guarantees on the distance of the returned solution to the optimal one. Approximation algorithms naturally arise in the field of theoretical computer science as a consequence of the widely believed P ≠ NP conjecture. Under this conjecture, a wide class of optimization problems cannot be solved exactly in polynomial time. The field of approximation algorithms, therefore, tries to understand how closely it is possible to approximate optimal solutions to such problems in polynomial time. In an overwhelming majority of the cases, the guarantee of such algorithms is a multiplicative one expressed as an approximation ratio or approximation factor i.e., the optimal solution is always guaranteed to be within a (predetermined) multiplicative factor of the returned solution. However, there are also many approximation algorithms that provide an additive guarantee on the quality of the returned solution. A notable example of an approximation algorithm that provides both is the classic approximation algorithm of Lenstra, Shmoys and Tardos for scheduling on unrelated parallel machines.

In the mathematical discipline of graph theory, a matching or independent edge set in an undirected graph is a set of edges without common vertices. In other words, a subset of the edges is a matching if each vertex appears in at most one edge of that matching. Finding a matching in a bipartite graph can be treated as a network flow problem.

In the mathematical discipline of graph theory, a feedback vertex set (FVS) of a graph is a set of vertices whose removal leaves a graph without cycles. Equivalently, each FVS contains at least one vertex of any cycle in the graph. The feedback vertex set number of a graph is the size of a smallest feedback vertex set. The minimum feedback vertex set problem is an NP-complete problem; it was among the first problems shown to be NP-complete. It has wide applications in operating systems, database systems, and VLSI chip design.

In computational complexity theory, Karp's 21 NP-complete problems are a set of computational problems which are NP-complete. In his 1972 paper, "Reducibility Among Combinatorial Problems", Richard Karp used Stephen Cook's 1971 theorem that the boolean satisfiability problem is NP-complete to show that there is a polynomial time many-one reduction from the boolean satisfiability problem to each of 21 combinatorial and graph theoretical computational problems, thereby showing that they are all NP-complete. This was one of the first demonstrations that many natural computational problems occurring throughout computer science are computationally intractable, and it drove interest in the study of NP-completeness and the P versus NP problem.

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 one has a finite set S and a list of subsets of S. Then, the set packing problem asks if some k subsets in the list are pairwise disjoint.

In computational complexity theory, the class APX is the set of NP optimization problems that allow polynomial-time approximation algorithms with approximation ratio bounded by a constant. In simple terms, problems in this class have efficient algorithms that can find an answer within some fixed multiplicative factor of the optimal answer.

<span class="mw-page-title-main">Kőnig's theorem (graph theory)</span> Theorem showing that maximum matching and minimum vertex cover are equivalent for bipartite graphs

In the mathematical area of graph theory, Kőnig's theorem, proved by Dénes Kőnig, describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs. It was discovered independently, also in 1931, by Jenő Egerváry in the more general case of weighted graphs.

Maximum cardinality matching is a fundamental problem in graph theory. We are given a graph G, and the goal is to find a matching containing as many edges as possible; that is, a maximum cardinality subset of the edges such that each vertex is adjacent to at most one edge of the subset. As each edge will cover exactly two vertices, this problem is equivalent to the task of finding a matching that covers as many vertices as possible.

In computational complexity theory, a gadget is a subunit of a problem instance that simulates the behavior of one of the fundamental units of a different computational problem. Gadgets are typically used to construct reductions from one computational problem to another, as part of proofs of NP-completeness or other types of computational hardness. The component design technique is a method for constructing reductions by using gadgets.

<span class="mw-page-title-main">Maximum cut</span> Problem of finding a maximum cut in a graph

In a graph, a maximum cut is a cut whose size is at least the size of any other cut. That is, it is a partition of the graph's vertices into two complementary sets S and T, such that the number of edges between S and T is as large as possible. Finding such a cut is known as the max-cut problem.

In computational complexity theory, the set splitting problem is the following decision problem: given a family F of subsets of a finite set S, decide whether there exists a partition of S into two subsets S1, S2 such that all elements of F are split by this partition, i.e., none of the elements of F is completely in S1 or S2. Set Splitting is one of Garey & Johnson's classical NP-complete problems. The problem is sometimes called hypergraph 2-colorability.

<span class="mw-page-title-main">Matroid parity problem</span> Largest independent set of paired elements

In combinatorial optimization, the matroid parity problem is a problem of finding the largest independent set of paired elements in a matroid. The problem was formulated by Lawler (1976) as a common generalization of graph matching and matroid intersection. It is also known as polymatroid matching, or the matchoid problem.

In graph theory, a rainbow-independent set (ISR) is an independent set in a graph, in which each vertex has a different color.

References

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.