3-dimensional matching

<h2 id="definition">Definition</h2>
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.

<h3>Example</h3>
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.

<h3>Comparison with bipartite matching</h3>
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 <a href="/facts/Bipartite_graph/xWcXV9MB">bipartite graph</a> 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 <a href="/facts/Matching_(graph_theory)/s0pUJ7hd">matching</a> 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.

<h3>Comparison with set packing</h3>
A 3-dimensional matching is a special case of a <a href="/facts/Set_packing/6SYrhrDN">set packing</a>: 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.

<h2 id="decision-problem">Decision problem</h2>
In computational complexity theory, 3-dimensional matching (3DM) is the name of the following <a href="/facts/Decision_problem/cQNWjbdE">decision problem</a>: 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 <a href="/facts/NP-complete/NFPv56DU">NP-complete</a>; it is one of <a href="/facts/Karp%27s_21_NP-complete_problems/dqu5bBh0">Karp's 21 NP-complete problems</a>.<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a> 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.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a><a class="footnote-ref" id="fnref:3" href="#fn:3">3</a><a class="footnote-ref" id="fnref:4" href="#fn:4">4</a> In this case, a 3-dimensional matching is not only a set packing, but also an <a href="/facts/Exact_cover/C7QcbDcN">exact cover</a>: the set M covers each element of X, Y, and Z exactly once.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> The proof is by reduction from <a href="/facts/Boolean_satisfiability_problem/wBVRjWoy">3SAT</a>. Given a 3SAT instance, we construct a 3DM instance as follows:<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a><a class="footnote-ref" id="fnref:7" href="#fn:7">7</a>

<ul><li>For each variable xi, there is a "variable gadget" shaped like a wheel. It is made of overlapping triplets. The number of triplets is twice the number of occurrences of xi in the formula. There are exactly two ways to cover all the vertices in the gadget: one is to choose all even-indexed triplets, and one is to choose all odd-indexed triplets. These two ways correspond to setting xi to "true" or "false". The "true" selection leaves uncovered exactly one vertex in every odd-indexed triplet, and the "false" selection leaves uncovered exactly one vertex in every even-indexed triplet.</li>
<li>For each clause xi u xj u xk, there is a "clause gadget" shaped like a rose. It is made of three overlapping triplets, one for each variable in the clause. It can be covered iff at least one of the nodes is left uncovered by the selection of the variable gadgets.</li>
<li>Since it is possible that two or more nodes are left uncovered, we also need a "garbage collection gadget". It is shaped like a larger rose. It is made of several overlapping triplets, one for each vertex that can be left uncovered in the variable gadget. The number of such gadgets is determined so that they can be covered exactly if and only if there is a satisfying assignment.</li></ul>
<h3>Special cases</h3>
There exist polynomial time algorithms for solving 3DM in dense hypergraphs.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a><a class="footnote-ref" id="fnref:9" href="#fn:9">9</a>

<h2 id="optimization-problem">Optimization problem</h2>
A maximum 3-dimensional matching is a largest 3-dimensional matching. In computational complexity theory, this is also the name of the following <a href="/facts/Optimization_problem/QzwJfFEE">optimization problem</a>: 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 <a href="/facts/NP-hard/mQeNPv4R">NP-hard</a>, 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 <a href="/facts/Bipartite_matching/s0pUJ7hd">bipartite matching</a> (maximum 2-dimensional matching), for example, the <a href="/facts/Hopcroft%E2%80%93Karp_algorithm/fEGdr2VP">Hopcroft–Karp algorithm</a>.

<h3>Approximation algorithms</h3>
There is a very simple polynomial-time 3-approximation algorithm for 3-dimensional matching: find any maximal 3-dimensional matching.<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a> Just like a maximal matching is within factor 2 of a maximum matching,<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a> 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.<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a>
However, attaining better approximation factors is probably hard: the problem is <a href="/facts/APX-complete/ggqAJ3A3">APX-complete</a>, that is, it is hard to <a href="/facts/Approximation_algorithm/BWlf7M32">approximate</a> within some constant.<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a><a class="footnote-ref" id="fnref:14" href="#fn:14">14</a><a class="footnote-ref" id="fnref:15" href="#fn:15">15</a>
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.<a class="footnote-ref" id="fnref:16" href="#fn:16">16</a>

<h3>Parallel algorithms</h3>
There are various algorithms for 3-d matching in the <a href="/facts/Massively_parallel_communication/K6uQlyXH">massively parallel communication</a> model.<a class="footnote-ref" id="fnref:17" href="#fn:17">17</a>

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/List_of_NP-complete_problems/pmR9Dlym">List of NP-complete problems</a></li>
<li><a href="/facts/Rainbow-independent_set/IGHKHF7f">Rainbow-independent set</a> – a problem that can be reduced from 3-dimensional matching.</li>
<li><a href="/facts/Numerical_3-dimensional_matching/bIySVJjg">Numerical 3-dimensional matching</a></li></ul>
<h2 id="notes">Notes</h2>

<ul><li>Ausiello, Giorgio; Crescenzi, Pierluigi; Gambosi, Giorgio; Kann, Viggo; Marchetti-Spaccamela, Alberto; Protasi, Marco (2003), Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, <a href="/facts/Springer_Science%2BBusiness_Media/nAesf6nT">Springer</a>.</li>
<li>Crescenzi, Pierluigi; Kann, Viggo; Halldórsson, Magnús; <a href="/facts/Marek_Karpinski/XPxNRbPA">Karpinski, Marek</a>; <a href="/facts/Gerhard_J._Woeginger/beUa9kJr">Woeginger, Gerhard</a> (2000), "Maximum 3-dimensional matching", <a href="https://www.csc.kth.se/~viggo/wwwcompendium/node143.html">A Compendium of NP Optimization Problems</a>.</li>
<li>Kann, Viggo (1991), "Maximum bounded 3-dimensional matching is MAX SNP-complete", Information Processing Letters, 37 (1): 27–35, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0020-0190%2891%2990246-E">10.1016/0020-0190(91)90246-E</a>.</li>
<li><a href="/facts/Richard_Karp/XtYCL0nA">Karp, Richard M.</a> (1972), "Reducibility among combinatorial problems", in Miller, Raymond E.; Thatcher, James W. (eds.), Complexity of Computer Computations, Plenum, pp. 85–103.</li>
<li><a href="/facts/Marek_Karpinski/XPxNRbPA">Karpinski, Marek</a>; Rucinski, Andrzej; Szymanska, Edyta (2009), "The Complexity of Perfect Matching Problems on Dense Hypergraphs", ISAAC '09 Proceedings of the 20th International Symposium on Algorithms, Lecture Notes in Computer Science, 5878: 626–636, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F978-3-642-10631-6_64">10.1007/978-3-642-10631-6_64</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-3-642-10630-9.</li>
<li>Keevash, Peter; Knox, Fiachra; Mycroft, Richard (2013), "Polynomial-time perfect matchings in dense hypergraphs", Proceedings of the forty-fifth annual ACM symposium on Theory of Computing, pp. 311–320, <a href="/facts/ArXiv_(identifier)/H6EtgnBe">arXiv</a>:<a href="https://arxiv.org/abs/1307.2608">1307.2608</a>, <a href="/facts/Bibcode_(identifier)/9HtdQSGB">Bibcode</a>:<a href="https://ui.adsabs.harvard.edu/abs/2013arXiv1307.2608K">2013arXiv1307.2608K</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F2488608.2488647">10.1145/2488608.2488647</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 9781450320290, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:5393523">5393523</a>.</li>
<li><a href="/facts/Christos_Papadimitriou/rXflR4or">Papadimitriou, Christos H.</a>; <a href="/facts/Kenneth_Steiglitz/zIFEom0n">Steiglitz, Kenneth</a> (1998), Combinatorial Optimization: Algorithms and Complexity, <a href="/facts/Dover_Publications/RwjvlSFv">Dover Publications</a>.</li></ul>
<h2 id="external-links">External links</h2>
<ul><li><a href="https://jsfiddle.net/Lamik/6z4agLue/embedded/result/">An interactive visualisation implemented in JavaScript</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Karp (1972). - Karp, Richard M. (1972), "Reducibility among combinatorial problems", in Miller, Raymond E.; Thatcher, James W. (eds.), Complexity of Computer Computations, Plenum, pp. 85–103 <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Karp (1972). - Karp, Richard M. (1972), "Reducibility among combinatorial problems", in Miller, Raymond E.; Thatcher, James W. (eds.), Complexity of Computer Computations, Plenum, pp. 85–103 <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">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. <a href="9780716710455" target="_blank">9780716710455</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Korte, Bernhard; Vygen, Jens (2006), Combinatorial Optimization: Theory and Algorithms (3rd ed.), Springer, Section 15.5. <a href="/wiki/Bernhard_Korte" target="_blank">/wiki/Bernhard_Korte</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Papadimitriou & Steiglitz (1998), Section 15.7. - Papadimitriou, Christos H.; Steiglitz, Kenneth (1998), Combinatorial Optimization: Algorithms and Complexity, Dover Publications <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">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. <a href="9780716710455" target="_blank">9780716710455</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Demaine, Erik (2016). "16. Complexity: P, NP, NP-completeness, Reductions". YouTube. <a href="https://www.youtube.com/watch?v=mr1FMrwi6Ew&t=2780" target="_blank">https://www.youtube.com/watch?v=mr1FMrwi6Ew&t=2780</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Karpinski, Rucinski & Szymanska (2009) - Karpinski, Marek; Rucinski, Andrzej; Szymanska, Edyta (2009), "The Complexity of Perfect Matching Problems on Dense Hypergraphs", ISAAC '09 Proceedings of the 20th International Symposium on Algorithms, Lecture Notes in Computer Science, 5878: 626–636, doi:10.1007/978-3-642-10631-6_64, ISBN 978-3-642-10630-9 <a href="https://doi.org/10.1007%2F978-3-642-10631-6_64" target="_blank">https://doi.org/10.1007%2F978-3-642-10631-6_64</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Keevash, Knox & Mycroft (2013) - Keevash, Peter; Knox, Fiachra; Mycroft, Richard (2013), "Polynomial-time perfect matchings in dense hypergraphs", Proceedings of the forty-fifth annual ACM symposium on Theory of Computing, pp. 311–320, arXiv:1307.2608, Bibcode:2013arXiv1307.2608K, doi:10.1145/2488608.2488647, ISBN 9781450320290, S2CID 5393523 <a href="https://arxiv.org/abs/1307.2608" target="_blank">https://arxiv.org/abs/1307.2608</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Kann (1991) - Kann, Viggo (1991), "Maximum bounded 3-dimensional matching is MAX SNP-complete", Information Processing Letters, 37 (1): 27–35, doi:10.1016/0020-0190(91)90246-E <a href="https://doi.org/10.1016%2F0020-0190%2891%2990246-E" target="_blank">https://doi.org/10.1016%2F0020-0190%2891%2990246-E</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Matching (graph theory)#Properties. <a href="/wiki/Matching_(graph_theory)#Properties" target="_blank">/wiki/Matching_(graph_theory)#Properties</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">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. <a href="978-0-7695-5135-7" target="_blank">978-0-7695-5135-7</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Crescenzi et al. (2000). - Crescenzi, Pierluigi; Kann, Viggo; Halldórsson, Magnús; Karpinski, Marek; Woeginger, Gerhard (2000), "Maximum 3-dimensional matching", A Compendium of NP Optimization Problems <a href="https://www.csc.kth.se/~viggo/wwwcompendium/node143.html" target="_blank">https://www.csc.kth.se/~viggo/wwwcompendium/node143.html</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">Ausiello et al. (2003), problem SP1 in Appendix B. - Ausiello, Giorgio; Crescenzi, Pierluigi; Gambosi, Giorgio; Kann, Viggo; Marchetti-Spaccamela, Alberto; Protasi, Marco (2003), Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
<li id="fn:15">Kann (1991) - Kann, Viggo (1991), "Maximum bounded 3-dimensional matching is MAX SNP-complete", Information Processing Letters, 37 (1): 27–35, doi:10.1016/0020-0190(91)90246-E <a href="https://doi.org/10.1016%2F0020-0190%2891%2990246-E" target="_blank">https://doi.org/10.1016%2F0020-0190%2891%2990246-E</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></li>
<li id="fn:16">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. <a href="/wiki/Janka_Chleb%C3%ADkov%C3%A1" target="_blank">/wiki/Janka_Chleb%C3%ADkov%C3%A1</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></li>
<li id="fn:17">Hanguir, Oussama; Stein, Clifford (2020-09-21). "Distributed Algorithms for Matching in Hypergraphs". arXiv:2009.09605 [cs.DS]. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></li>
</ol>

3-dimensional matching open-in-new

3-dimensional matching