Editing Matching (graph theory) (section)

=== Maximal matchings ===

A maximal matching can be found with a simple [[greedy algorithm]]. A maximum matching is also a maximal matching, and hence it is possible to find a ''largest'' maximal matching in polynomial time. However, no polynomial-time algorithm is known for finding a '''minimum maximal matching''', that is, a maximal matching that contains the ''smallest'' possible number of edges.

A maximal matching with ''k'' edges is an [[edge dominating set]] with ''k'' edges. Conversely, if we are given a minimum edge dominating set with ''k'' edges, we can construct a maximal matching with ''k'' edges in polynomial time. Therefore, the problem of finding a minimum maximal matching is essentially equal to the problem of finding a minimum edge dominating set.<ref>{{citation
 | first1=Mihalis | last1=Yannakakis
 | first2=Fanica | last2=Gavril
 | title=Edge dominating sets in graphs
 | journal=SIAM Journal on Applied Mathematics
 | year=1980
 | volume=38
 | pages=364–372
 | doi=10.1137/0138030
 | issue=3
| url=http://cgi.di.uoa.gr/~vassilis/co/dominating-sets.pdf
 }}.</ref> Both of these two optimization problems are known to be [[NP-hard]]; the decision versions of these problems are classical examples of [[NP-complete]] problems.<ref>{{citation
 | last1=Garey | first1=Michael R. | author-link1=Michael R. Garey
 | last2=Johnson | first2=David S. | author-link2=David S. Johnson
 | year = 1979
 | title = Computers and Intractability: A Guide to the Theory of NP-Completeness
 | publisher = W.H. Freeman
 | isbn=0-7167-1045-5
| title-link=Computers and Intractability: A Guide to the Theory of NP-Completeness }}. Edge dominating set (decision version) is discussed under the dominating set problem, which is the problem GT2 in Appendix&nbsp;A1.1. Minimum maximal matching (decision version) is the problem GT10 in Appendix&nbsp;A1.1.</ref> Both problems can be [[approximation algorithm|approximated]] within factor 2 in polynomial time: simply find an arbitrary maximal matching ''M''.<ref>{{citation
 | last1=Ausiello | first1=Giorgio
 | last2=Crescenzi | first2=Pierluigi
 | last3=Gambosi | first3=Giorgio
 | last4=Kann | first4=Viggo
 | last5=Marchetti-Spaccamela | first5=Alberto
 | last6=Protasi | first6=Marco
 | title=Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties
 | publisher=Springer
 | year=2003
}}. Minimum edge dominating set (optimisation version) is the problem GT3 in Appendix B (page 370). Minimum maximal matching (optimisation version) is the problem GT10 in Appendix B (page 374). See also [https://www.csc.kth.se/~viggo/wwwcompendium/node13.html Minimum Edge Dominating Set] and [https://www.csc.kth.se/~viggo/wwwcompendium/node21.html Minimum Maximal Matching] in the [https://www.csc.kth.se/~viggo/wwwcompendium/ web compendium].</ref>