Maximum cardinality matching

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.

Maximum cardinality matching is a fundamental problem in graph theory. We are given a graph Template:Mvar, and the goal is to find a matching containing as many edges as possible; that is, a maximum cardinality subset of the edges such that each vertex is adjacent to at most one edge of the subset. As each edge will cover exactly two vertices, this problem is equivalent to the task of finding a matching that covers as many vertices as possible.

An important special case of the maximum cardinality matching problem is when Template:Mvar is a bipartite graph, whose vertices Template:Mvar are partitioned between left vertices in Template:Mvar and right vertices in Template:Mvar, and edges in Template:Mvar 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.

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 Template:Math can be converted to a flow network as follows.

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

The Ford–Fulkerson algorithm proceeds by repeatedly finding an augmenting path from some Template:Math to some Template:Math and updating the matching Template:Mvar by taking the symmetric difference of that path with Template:Mvar (assuming such a path exists). As each path can be found in Template:Math time, the running time is Template:Math, and the maximum matching consists of the edges of Template:Mvar that carry flow from Template:Mvar to Template:Mvar.

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 $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 Template:Mvar, which for Template:Math is

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

Using Boolean operations on words of size $\lambda$ the complexity is further improved to

$O(\min \{|X|k,\frac{|X||Y|}{\lambda },E\}+k^2+\frac{k^{2.5}}{\lambda }).$

More efficient algorithms exist for special kinds of bipartite graphs:

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

Algorithms for arbitrary graphs

The blossom algorithm finds a maximum-cardinality matching in general (not necessarily bipartite) graphs. It runs in time $O(|V{|}^2\cdot |E|)$. A better performance of Template:Math for general graphs, matching the performance of the Hopcroft–Karp algorithm on bipartite graphs, can be achieved with the much more complicated algorithm of Micali and Vazirani. The same bound was achieved by an algorithm by Template:Ill and an algorithm by Gabow and Tarjan.

An alternative approach uses randomization and is based on the fast matrix multiplication algorithm. This gives a randomized algorithm for general graphs with complexity $O(V^{2.372})$. This is better in theory for sufficiently dense graphs, but in practice the algorithm is slower.

Other algorithms for the task are reviewed by Duan and Pettie (see Table I). In terms of approximation algorithms, they also point out that the blossom algorithm and the algorithms by Micali and Vazirani can be seen as approximation algorithms running in linear time for any fixed error bound.

Applications and generalizations

• By finding a maximum-cardinality matching, it is possible to decide whether there exists a perfect matching.
• The problem of finding a matching with maximum weight in a weighted graph is called the maximum weight matching problem, and its restriction to bipartite graphs is called the assignment problem. If each vertex can be matched to several vertices at once, then this is a generalized assignment problem.
• A priority matching is a particular maximum-cardinality matching in which prioritized vertices are matched first.
• The problem of finding a maximum-cardinality matching in hypergraphs is NP-complete even for 3-uniform hypergraphs.