# Maximum cardinality matching

Maximum cardinality matching is a fundamental problem in graph theory.

Given a bipartite graph $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).

## 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 $\ O(E)$ time, the running time is $\ O(VE)$ . This solution is equivalent to adding a super source $s$ with edges to all vertices in $\ X$ , and a super sink $\ t$ with edges from all vertices in $\ Y$ , and finding a maximal flow from $\ s$ to $\ t$ . All edges with flow from $\ X$ to $\ Y$ then constitute a maximum matching.

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

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

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

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

6. Using boolean operations on words of size $\lambda$ the complexity is further improved to $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 $n$ -vertex bipartite planar graphs can be solved in time $O(n\log ^{3}n)$ .

## 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.