View source for Maximum cardinality matching

{{short description|Graph theory problem: find a matching containing the most edges}}
[[File:Maximum cardinality matching.svg|thumb|470px|The graph on the left has maximum cardinality matching one less than the one on the right, despite the fact that they both have the same number of vertices.]]

'''Maximum cardinality matching''' is a fundamental problem in [[graph theory]].<ref name="Wes01">{{citation|last=West|first=Douglas Brent|title=Introduction to Graph Theory|year=1999|at=Chapter 3|edition=2nd|publisher=Prentice Hall|isbn=0-13-014400-2}}</ref>
We are given a [[graph (graph theory)|graph]] {{mvar|G}}, and the goal is to find a [[Matching (graph theory)|matching]] containing as many edges as possible; that is, a maximum [[cardinality]] subset of the edges such that each [[Vertex (graph theory)|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.

An important [[special case]] of the maximum cardinality matching problem is when {{mvar|G}} is a [[bipartite graph]], whose vertices {{mvar|V}} are partitioned between left vertices in {{mvar|X}} and right vertices in {{mvar|Y}}, and edges in {{mvar|E}} always connect a left vertex to a right vertex. In this case, the problem can be efficiently solved with simpler algorithms than in the general case.

== Algorithms for bipartite graphs ==

=== Flow-based algorithm ===
The simplest way to compute a maximum cardinality matching is to follow the [[Ford–Fulkerson algorithm]]. This algorithm solves the more general problem of [[maximum flow problem|computing the maximum flow]]. A bipartite graph {{math|(''X'' + ''Y'', ''E'')}} can be converted to a [[flow network]] as follows.

* Add a source vertex {{mvar|s}}; add an edge from {{mvar|s}} to each vertex in {{mvar|X}}.
* Add a sink vertex {{mvar|t}}; add an edge from each vertex in {{mvar|Y}} to {{mvar|t}}.
* Assign a capacity of 1 to each edge. 

Since each edge in the network has integral capacity, there exists a maximum flow where all flows are integers; these integers must be either 0 or 1 since the all capacities are 1. Each integral flow defines a matching in which an edge is in the matching [[if and only if]] its flow is 1. It is a matching because:

* The incoming flow into each vertex in {{mvar|X}} is at most 1, so the outgoing flow is at most 1 too, so at most one edge adjacent to each vertex in {{mvar|X}} is present. 
* The outgoing flow from each vertex in {{mvar|Y}} is at most 1, so the incoming flow is at most 1 too, so at most one edge adjacent to each vertex in {{mvar|Y}} is present. 

The Ford–Fulkerson algorithm proceeds by repeatedly finding an augmenting path from some {{math|''x'' ∈ ''X''}} to some {{math|''y'' ∈ {{mvar|Y}}}} and updating the matching {{mvar|M}} by taking the [[symmetric difference]] of that path with {{mvar|M}} (assuming such a path exists). As each path can be found in {{math|[[Big O notation|''O'']](''E'')}} time, the running time is {{math|''O''(''VE'')}}, and the maximum matching consists of the edges of {{mvar|E}} that carry flow from {{mvar|X}} to {{mvar|Y}}.

=== Advanced algorithms ===
An improvement to this algorithm is given by the more elaborate [[Hopcroft–Karp algorithm]], which searches for multiple augmenting paths simultaneously. This algorithm runs in <math>O(\sqrt{V}E)</math> time.

The algorithm of Chandran and Hochbaum<ref name="Chandran" /> for bipartite graphs runs in time that depends on the size of the maximum matching {{mvar|k}}, which for {{math|{{abs|''X''}} < {{abs|''Y''}}}} is 
:<math>O\left(\min\{|X|k,E\}+ \sqrt{k} \min \{k^2,E\}\right).</math>
Using Boolean operations on words of size <math>\lambda</math> the complexity is further improved to<ref name="Chandran" />
:<math>O\left(\min \left\{|X|k, \frac{|X||Y|}{\lambda}, E\right\} + k^2 + \frac{k^{2.5}}{\lambda}\right).</math>

More efficient algorithms exist for special kinds of bipartite graphs:
* For [[sparse graph|sparse]] bipartite graphs, the maximum matching problem can be solved in <math>\tilde{O}(E^{10/7})</math> with Madry's algorithm based on electric flows.<ref>{{citation|last=Madry|first=A|title=Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on|pages=253–262|year=2013|contribution=Navigating Central Path with Electrical Flows: From Flows to Matchings, and Back|arxiv=1307.2205|bibcode=2013arXiv1307.2205M}}</ref> 
* For [[planar graphs|planar]] bipartite graphs, the problem can be solved in time {{math|''O''(''n'' log{{sup|3}} ''n'')}} where {{mvar|n}} is the number of vertices, by reducing the problem to [[maximum flow]] with multiple sources and sinks.<ref>{{citation|last1=Borradaile|first1=Glencora|title=Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time|journal=[[SIAM Journal on Computing]]|volume=46|issue=4|pages=1280–1303|year=2017|arxiv=1105.2228|doi=10.1137/15M1042929|mr=3681377|last2=Klein|first2=Philip N.|last3=Mozes|first3=Shay|last4=Nussbaum|first4=Yahav|last5=Wulff–Nilsen|first5=Christian|s2cid=207071917}}</ref>

== Algorithms for arbitrary graphs ==

The [[blossom algorithm]] finds a maximum-cardinality matching in general (not necessarily bipartite) graphs. It runs in time <math>O(|V|^2 \cdot |E|)</math>. A better performance of {{math|<var>O</var>({{radical|<var>V</var>}}<var>E</var>)}} for general graphs, matching the performance of the [[Hopcroft–Karp algorithm]] on bipartite graphs, can be achieved with the much more complicated algorithm of Micali and Vazirani.<ref>{{citation|last1=Micali|first1=S.|title=[[Symposium on Foundations of Computer Science|Proc. 21st IEEE Symp. Foundations of Computer Science]]|pages=17–27|year=1980|contribution=An <math>\scriptstyle O(\sqrt{|V|}\cdot|E|)</math> algorithm for finding maximum matching in general graphs|doi=10.1109/SFCS.1980.12|last2=Vazirani|first2=V. V.|s2cid=27467816|author1-link=Silvio Micali|author2-link=Vijay Vazirani}}.</ref> The same bound was achieved by an algorithm by {{ill|lt=Blum|Norbert Blum (computer scientist)|de|Norbert Blum}}<ref>{{citation
 | last = Blum | first = Norbert
 | editor-last = Paterson | editor-first = Mike | editor-link = Mike Paterson
 | contribution = A new approach to maximum matching in general graphs
 | contribution-url = https://web.eecs.umich.edu/~pettie/matching/Blum-matching-ICALP90.pdf
 | doi = 10.1007/BFb0032060
 | pages = 586–597
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = Automata, Languages and Programming, 17th International Colloquium, ICALP90, Warwick University, England, UK, July 16–20, 1990, Proceedings
 | volume = 443
 | year = 1990}}</ref> and an algorithm by [[Harold N. Gabow|Gabow]] and [[Robert Tarjan|Tarjan]].<ref>{{Cite journal|first1=Harold N|last1=Gabow|author1-link=Harold N. Gabow|first2=Robert E|last2=Tarjan|date=1991-10-01|title=Faster scaling algorithms for general graph matching problems|url=https://web.eecs.umich.edu/~pettie/matching/Gabow-Tarjan-scaling-general-graph-matching.pdf|journal=Journal of the ACM|volume=38|issue=4|pages=815–853|language=EN|doi=10.1145/115234.115366|s2cid=18350108}}</ref>

An alternative approach uses [[randomized algorithm|randomization]] and is based on the fast [[matrix multiplication]] algorithm. This gives a randomized algorithm for general graphs with complexity <math>O(V^{2.372})</math>.<ref name="Mucha">{{citation|last1=Mucha|first1=M.|title=[[Symposium on Foundations of Computer Science|Proc. 45th IEEE Symp. Foundations of Computer Science]]|pages=248–255|year=2004|contribution=Maximum Matchings via Gaussian Elimination|contribution-url=https://www.mimuw.edu.pl/~mucha/pub/mucha_sankowski_focs04.pdf|last2=Sankowski|first2=P.}}</ref> This is better in theory for sufficiently [[dense graph]]s, but in practice the algorithm is slower.<ref name="Chandran">{{citation|last1=Chandran|first1=Bala G.|title=Practical and theoretical improvements for bipartite matching using the pseudoflow algorithm|year=2011|arxiv=1105.1569|bibcode=2011arXiv1105.1569C|quote=the theoretically efficient algorithms listed above tend to perform poorly in practice|last2=Hochbaum|first2=Dorit S.|author2-link=Dorit S. Hochbaum}}.</ref>

Other algorithms for the task are reviewed by Duan and Pettie<ref>{{Cite journal|last1=Duan|first1=Ran|last2=Pettie|first2=Seth|date=2014-01-01|title=Linear-Time Approximation for Maximum Weight Matching|url=https://web.eecs.umich.edu/~pettie/papers/ApproxMWM-JACM.pdf|journal=Journal of the ACM|volume=61|pages=1–23|language=EN|doi=10.1145/2529989|s2cid=207208641}}</ref> (see Table I). In terms of [[approximation algorithm]]s, they also point out that the [[blossom algorithm]] and the algorithms by Micali and Vazirani can be seen as [[approximation algorithm]]s running in linear time for any fixed error bound.

== Applications and generalizations ==

* By finding a maximum-cardinality matching, it is possible to decide whether there exists a [[perfect matching]].
* The problem of finding a matching with maximum weight in a '''[[weighted graph]]''' is called the [[maximum weight matching|maximum weight matching problem]], and its restriction to bipartite graphs is called the [[assignment problem]]. If each vertex can be matched to several vertices at once, then this is a [[generalized assignment problem]].
* A [[priority matching]] is a particular maximum-cardinality matching in which prioritized vertices are matched first.
* The problem of finding a maximum-cardinality [[matching in hypergraphs]] is NP-complete even for 3-uniform hypergraphs.<ref>{{Citation|last=Karp|first=Richard M.|title=Reducibility among Combinatorial Problems|date=1972|work=Complexity of Computer Computations: Proceedings of a symposium on the Complexity of Computer Computations, held March 20–22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, and sponsored by the Office of Naval Research, Mathematics Program, IBM World Trade Corporation, and the IBM Research Mathematical Sciences Department|pages=85–103|editor-last=Miller|editor-first=Raymond E.|series=The IBM Research Symposia Series|place=Boston, MA|publisher=Springer US|language=en|doi=10.1007/978-1-4684-2001-2_9|isbn=978-1-4684-2001-2|editor2-last=Thatcher|editor2-first=James W.|editor3-last=Bohlinger|editor3-first=Jean D.}}</ref>

== References ==
{{Reflist}}

[[Category:Matching (graph theory)]]