Maximum-cardinality matching

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 computing the maximum flow. A bipartite graph (X + Y, E) can be converted to a flow network as follows.

• Add a source vertex s; add an edge from s to each vertex in X.
• Add a sink vertex t; add an edge from each vertex in Y to 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 X is at most 1, so the outgoing flow is at most 1 too, so at most one edge adjacent to each vertex in X is present.
• The outgoing flow from each vertex in Y is at most 1, so the incoming flow is at most 1 too, so at most one edge adjacent to each vertex in Y is present.

The Ford–Fulkerson algorithm proceeds by repeatedly finding an augmenting path from some x ∈ X to some y ∈ Y 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), and the maximum matching consists of the edges of E that carry flow from X to 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 ${\displaystyle O({\sqrt {V}}E)}$ time.

The algorithm of Chandran and Hochbaum for bipartite graphs runs in time that depends on the size of the maximum matching k, which for |X| < |Y| is

${\displaystyle O\left(\min\{|X|k,E\}+{\sqrt {k}}\min\{k^{2},E\}\right).}$

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).}$

More efficient algorithms exist for special kinds of bipartite graphs:

• For sparse bipartite graphs, the maximum matching problem can be solved in ${\displaystyle {\tilde {O}}(E^{10/7})}$ with Madry's algorithm based on electric flows.
• For planar bipartite graphs, the problem can be solved in time O(n log³ n) where n is the number of vertices, by reducing the problem to maximum flow with multiple sources and sinks.