Editing Matching (graph theory) (section)

== Algorithms and computational complexity ==
{{anchor|Bipartite matching}}
=== Maximum-cardinality matching ===
{{Main|Maximum cardinality matching}}
A fundamental problem in [[combinatorial optimization]] is finding a ''maximum matching''. This problem has various algorithms for different classes of graphs.

In an ''unweighted bipartite graph'', the optimization problem is to find a [[maximum cardinality matching]].  The problem is solved by the [[Hopcroft-Karp algorithm]] in time {{math|<var>O</var>({{radical|<var>V</var>}}<var>E</var>)}} time, and there are more efficient [[randomized algorithm]]s, [[approximation algorithm]]s, and algorithms for special classes of graphs such as bipartite [[planar graph]]s, as described in the main article.

=== Maximum-weight matching ===
{{Main|Maximum weight matching}}
In a [[weighted graph|''weighted'']] ''bipartite graph,'' the optimization problem is to find a maximum-weight matching; a dual problem is to find a minimum-weight matching. This problem is often called '''maximum weighted bipartite matching''', or the '''[[assignment problem]]'''. The [[Hungarian algorithm]] solves the assignment problem and it was one of the beginnings of combinatorial optimization algorithms. It uses a modified [[shortest path]] search in the augmenting path algorithm. If the [[Bellman–Ford algorithm]] is used for this step, the running time of the Hungarian algorithm becomes <math>O(V^2 E)</math>, or the edge cost can be shifted with a potential to achieve <math>O(V^2 \log{V} + V E)</math> running time with the [[Dijkstra algorithm]] and [[Fibonacci heap]].<ref name="Fredman87">{{citation|last1=Fredman|first1=Michael L.|title=Fibonacci heaps and their uses in improved network optimization algorithms|journal=[[Journal of the ACM]]|volume=34|issue=3|pages=596–615|year=1987|doi=10.1145/28869.28874|last2=Tarjan|first2=Robert Endre|s2cid=7904683|doi-access=free}}</ref>

In a ''non-bipartite weighted graph'', the problem of '''[[maximum weight matching]]''' can be solved in time  <math>O(V^{2}E)</math> using [[Edmonds's matching algorithm|Edmonds' blossom algorithm]].

=== 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>

=== Counting problems ===
{{main|Hosoya index}}
The number of matchings in a graph is known as the [[Hosoya index]] of the graph. It is [[Sharp-P-complete|#P-complete]] to compute this quantity, even for bipartite graphs.<ref>[[Leslie Valiant]], ''The Complexity of Enumeration and Reliability Problems'',  SIAM J. Comput., 8(3), 410–421</ref> It is also #P-complete to count [[Perfect matching|perfect matchings]], even in [[bipartite graph]]s, because computing the [[Permanent (mathematics)|permanent]] of an arbitrary 0–1 matrix (another #P-complete problem) is the same as computing the number of perfect matchings in the bipartite graph having the given matrix as its [[biadjacency matrix]]. However, there exists a fully polynomial time randomized approximation scheme for counting the number of bipartite matchings.<ref>{{cite journal
| last1        = Bezáková
| first1       = Ivona
| last2        = Štefankovič
| first2       = Daniel
| last3        = Vazirani
| first3       = Vijay V.
| author-link3  = Vijay Vazirani
| last4        = Vigoda
| first4       = Eric
| year         = 2008
| title        = Accelerating Simulated Annealing for the Permanent and Combinatorial Counting Problems
| journal      = [[SIAM Journal on Computing]]
| volume       = 37
| issue        = 5
| pages        = 1429–1454
| doi          = 10.1137/050644033
| citeseerx= 10.1.1.80.687
| s2cid = 755231
}}</ref> A remarkable theorem of [[Pieter Kasteleyn|Kasteleyn]] states that the number of perfect matchings in a [[planar graph]] can be computed exactly in polynomial time via the [[FKT algorithm]].

The number of perfect matchings in a [[complete graph]] ''K''<sub>''n''</sub> (with ''n'' even) is given by the [[double factorial]] (''n''&nbsp;&minus;&nbsp;1)!!.<ref>{{citation|title=A combinatorial survey of identities for the double factorial|first=David|last=Callan|arxiv=0906.1317|year=2009|bibcode=2009arXiv0906.1317C}}.</ref> The numbers of matchings in complete graphs, without constraining the matchings to be perfect, are given by the [[Telephone number (mathematics)|telephone number]]s.<ref>{{citation
 | last1 = Tichy | first1 = Robert F.
 | last2 = Wagner | first2 = Stephan
 | doi = 10.1089/cmb.2005.12.1004
 | pmid = 16201918
 | issue = 7
 | journal = [[Journal of Computational Biology]]
 | pages = 1004–1013
 | title = Extremal problems for topological indices in combinatorial chemistry
 | url = http://www.math.tugraz.at/fosp/pdfs/tugraz_main_0052.pdf
 | volume = 12
 | year = 2005}}.</ref>

The number of perfect matchings in a graph is also known as the [[hafnian]] of its [[adjacency matrix]].

=== Finding all maximally matchable edges ===
{{Main|Maximally matchable edge}}
One of the basic problems in matching theory is to find in a given graph all edges that may be extended to a maximum matching in the graph (such edges are called [[maximally matchable edge]]s, or '''allowed''' edges). Algorithms for this problem include:

* For general graphs, a deterministic algorithm in time <math>O(VE)</math> and a randomized algorithm in time <math>\tilde{O}(V^{2.376}) </math>.<ref>{{citation
| last1 = Rabin | first1 = Michael O.
| last2 = Vazirani | first2 = Vijay V.
| title = Maximum matchings in general graphs through randomization
| journal = [[Journal of Algorithms]]
| volume = 10
| year = 1989
| issue = 4
| pages = 557–567
|  doi = 10.1016/0196-6774(89)90005-9| citeseerx = 10.1.1.228.1996
}}</ref><ref>
{{citation
| last1 = Cheriyan | first1 = Joseph
| title = Randomized <math>\widetilde O(M(|V|))</math> algorithms for problems in matching theory
| journal = [[SIAM Journal on Computing]]
| volume = 26
| year = 1997
| number = 6
| pages = 1635–1655
| doi = 10.1137/S0097539793256223
}}</ref>
* For bipartite graphs, if a single maximum matching is found, a deterministic algorithm runs in time <math>O(V+E)</math>.<ref>{{citation
| last1 = Tassa | first1= Tamir
| title = Finding all maximally-matchable edges in a bipartite graph
| journal = [[Theoretical Computer Science]]
| volume = 423
| year = 2012
| pages = 50–58
| doi = 10.1016/j.tcs.2011.12.071
| doi-access = free
}}</ref>

=== Online bipartite matching ===
The problem of developing an [[online algorithm]] for matching was first considered by [[Richard M. Karp]], [[Umesh Vazirani]], and [[Vijay Vazirani]] in 1990.<ref>{{cite conference|last1=Karp|first1=Richard M.|author1-link=Richard M. Karp|last2=Vazirani|first2=Umesh V.|author2-link=Umesh Vazirani|last3=Vazirani|first3=Vijay V.|author3-link=Vijay Vazirani|contribution=An optimal algorithm for on-line bipartite matching|contribution-url=https://people.eecs.berkeley.edu/~vazirani/pubs/online.pdf|doi=10.1145/100216.100262|pages=352–358|title=Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC 1990)|year=1990|isbn=0-89791-361-2 }}</ref> 

In the online setting, nodes on one side of the bipartite graph arrive one at a time and must either be immediately matched to the other side of the graph or discarded. This is a natural generalization of the [[secretary problem]] and has applications to online ad auctions. The best online algorithm, for the unweighted maximization case with a random arrival model, attains a [[Competitive analysis (online algorithm)|competitive ratio]] of {{math|0.696}}.<ref>{{cite conference|last1=Mahdian|first1=Mohammad|last2=Yan|first2=Qiqi|doi=10.1145/1993636.1993716|title=Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing|pages=597–606|contribution=Online bipartite matching with random arrivals: an approach based on strongly factor-revealing LPs|year=2011|doi-access=free}}</ref>