Maximum-cardinality matching

An important special case of the maximum-cardinality matching problem is when G is a bipartite graph representing a binary relation, whose vertices V are partitioned between left vertices in X and right vertices in Y, and edges in 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.

The calculation of a maximum matching for a given graph is a fundamental task in computational graph theory. There are nonconstructive characterization theorems for the size of a maximum matching. This article is about computation of maximum matchings.

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