Maximum cardinality matching

Maximum cardinality matching is a fundamental problem in graph theory.

The simplest way to compute a maximum cardinality matching is to follow the Ford–Fulkerson algorithm.

This algorithm solves the more general problem of computing the maximum flow.

A bipartite graph (X + Y, E) can be converted to a flow network as follows.

The algorithm of Chandran and Hochbaum[2] for bipartite graphs runs in time that depends on the size of the maximum matching k, which for |X| < |Y| is Using Boolean operations on words of size

the complexity is further improved to[2] More efficient algorithms exist for special kinds of bipartite graphs: The blossom algorithm finds a maximum-cardinality matching in general (not necessarily bipartite) graphs.

[7] An alternative approach uses randomization and is based on the fast matrix multiplication algorithm.

[8] This is better in theory for sufficiently dense graphs, but in practice the algorithm is slower.

[2] Other algorithms for the task are reviewed by Duan and Pettie[9] (see Table I).

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.