# Maximum cardinality matching

(Redirected from Maximum matching)

Maximum cardinality matching is a fundamental problem in graph theory.

Given a bipartite graph ${\displaystyle G=(V=(X,Y),E)}$, the goal is to find a matching with as many edges as possible (equivalently: a matching that covers as many vertices as possible).[1]

## Algorithms

1. The Ford–Fulkerson algorithm finds a maximum-cardinality matching by repeatedly finding an augmenting path from some xX to some yY and updating the matching M by taking the symmetric difference of that path with M (assuming such a path exists). As each path can be found in ${\displaystyle \ O(E)}$  time, the running time is ${\displaystyle \ O(VE)}$ . This solution is equivalent to adding a super source ${\displaystyle s}$  with edges to all vertices in ${\displaystyle \ X}$ , and a super sink ${\displaystyle \ t}$  with edges from all vertices in ${\displaystyle \ Y}$ , and finding a maximal flow from ${\displaystyle \ s}$  to ${\displaystyle \ t}$ . All edges with flow from ${\displaystyle \ X}$  to ${\displaystyle \ Y}$  then constitute a maximum matching.

2. An improvement over this is the Hopcroft–Karp algorithm, which runs in ${\displaystyle O({\sqrt {V}}E)}$  time. Micali and Vazirani's matching algorithm also runs in time O(VE) time.[2]

3. An alternative randomized approach is based on the fast matrix multiplication algorithm and gives ${\displaystyle O(V^{2.376})}$  complexity,[3] which is better in theory for sufficiently dense graphs, but in practice the algorithm is slower.[4]

4. For sparse graphs, ${\displaystyle {\tilde {O}}(E^{10/7})}$  is possible with Madry's algorithm based on electric flows.[5]

5. The algorithm of Chandran and Hochbaum[4] runs in time that depends on the size of the maximum matching ${\displaystyle k}$ , which for ${\displaystyle |X|<|Y|}$  is ${\displaystyle O\left(\min\{|X|k,E\}+{\sqrt {k}}\min\{k^{2},E\}\right)}$ .

6. Using boolean operations on words of size ${\displaystyle \lambda }$  the complexity is further improved to ${\displaystyle O\left(\min \left\{|X|k,{\frac {|X||Y|}{\lambda }},E\right\}+k^{2}+{\frac {k^{2.5}}{\lambda }}\right)}$ .[citation needed]

7. By reducing the problem to maximum flow with multiple sources and sinks, the maximum matching problem in ${\displaystyle n}$ -vertex bipartite planar graphs can be solved in time ${\displaystyle O(n\log ^{3}n)}$ .[6]

## Applications and generalizations

• By finding a maximum-cardinality matching, it is possible to decide whether there exists a perfect matching.
• The blossom algorithm finds a maximum-cardinality matching in general (not bipartite) graphs.
• The assignment problem finds a maximum-weight matching in a bipartite weighted graph.

## References

1. ^ West, Douglas Brent (1999), Introduction to Graph Theory (2nd ed.), Prentice Hall, Chapter 3, ISBN 0-13-014400-2
2. ^ Micali, S.; Vazirani, V. V. (1980), "An ${\displaystyle \scriptstyle O({\sqrt {|V|}}\cdot |E|)}$  algorithm for finding maximum matching in general graphs", Proc. 21st IEEE Symp. Foundations of Computer Science, pp. 17–27, doi:10.1109/SFCS.1980.12.
3. ^ Mucha, M.; Sankowski, P. (2004), "Maximum Matchings via Gaussian Elimination" (PDF), Proc. 45th IEEE Symp. Foundations of Computer Science, pp. 248–255
4. ^ a b Chandran, Bala G.; Hochbaum, Dorit S. (2011), Practical and theoretical improvements for bipartite matching using the pseudoflow algorithm, arXiv:1105.1569, Bibcode:2011arXiv1105.1569C, the theoretically efficient algorithms listed above tend to perform poorly in practice.
5. ^ Madry, A (2013), "Navigating Central Path with Electrical Flows: From Flows to Matchings, and Back", Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on, pp. 253–262, arXiv:1307.2205, Bibcode:2013arXiv1307.2205M
6. ^ Borradaile, Glencora; Klein, Philip N.; Mozes, Shay; Nussbaum, Yahav; Wulff–Nilsen, Christian (2017), "Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time", SIAM Journal on Computing, 46 (4): 1280–1303, arXiv:1105.2228, doi:10.1137/15M1042929, MR 3681377