Maximum-cardinality matching

Maximum-cardinality matching is a fundamental problem in computational graph theory. A graph is a collection of vertices, or dots, and edges, which are the lines connecting them. A matching is a subset of these edges where no two edges share a common vertex. In this type of matching, each vertex is adjacent to at most one edge. The goal of maximum-cardinality matching is to find a matching that contains as many edges as possible. Because every edge connects exactly two vertices, finding the largest number of edges is the same as covering as many vertices as possible.

One important special case involves bipartite graphs. In a bipartite graph, the vertices are partitioned into two distinct sets, often called left and right. Every edge in the graph must connect a vertex from the left set to a vertex in the right set. These graphs are easier to solve than general graphs. We can use a flow-based algorithm to find the matching. One such method is the Ford–Fulkerson algorithm, which solves the broader problem of maximum flow. To use this, we convert the bipartite graph into a flow network. We add a source vertex and connect it to every vertex in the left set. We also add a sink vertex and connect every vertex in the right set to it. Each edge is assigned a capacity of 1. Since the capacities are integers, the maximum flow will also consist of integers that are either 0 or 1. Each edge with a flow of 1 becomes part of the matching. The algorithm works by repeatedly finding an augmenting path from the source to the sink. It updates the matching by taking the symmetric difference of the current matching and the new path.

Several advanced algorithms exist to make this process faster. The Hopcroft–Karp algorithm is a significant improvement over the basic Ford–Fulkerson method. It speeds up the process by searching for multiple augmenting paths at the same time. For bipartite graphs, the running time of Hopcroft–Karp is $O(E\sqrt{V})$. Other researchers have developed even more specialized tools. Chandran and Hochbaum created an algorithm where the speed depends on the size of the maximum matching, denoted as $m$. For bipartite graphs, this complexity is $O(m\sqrt{E})$. If we use Boolean operations on words of size $w$, the complexity improves further to $O(m\sqrt{E}/w)$.

We can also find faster solutions for specific types of bipartite graphs. If a bipartite graph is sparse, Madry's algorithm can solve the problem using electric flows. This algorithm runs in $O(E^{1+o(1)})$ time. For planar bipartite graphs, which are graphs that can be drawn without edges crossing, the problem is also quite efficient. We can reduce the planar problem to a maximum flow problem with multiple sources and sinks. This allows us to solve the matching in $O(V^{1.5})$ time, where $V$ is the number of vertices.

General graphs are much more difficult to solve because they lack the two-set structure of bipartite graphs. The blossom algorithm is a famous method used to find a maximum-cardinality matching in these general graphs. It operates in $O(E^2)$ time. However, much faster methods have been discovered. The Micali and Vazirani algorithm is quite complicated but achieves a running time of $O(E\sqrt{V})$. This matches the performance of the Hopcroft–Karp algorithm used for bipartite graphs. Other researchers, such as Gabow and Tarjan, also reached this same performance bound. There is even a randomized approach based on the fast matrix multiplication algorithm. This method has a complexity of $O(V^{\omega})$, where $\omega$ is the exponent for matrix multiplication. While this is better in theory for very dense graphs, it is often slower in practical use.

Finding a maximum matching allows us to answer many other mathematical questions. For example, it can help us decide if a perfect matching exists. A perfect matching is a specific case where every single vertex in the graph is matched.

We can also study weighted graphs, where edges have different values. Finding the matching with the highest total value is called the maximum-weight matching problem. When this is applied specifically to bipartite graphs, it is known as the assignment problem. If we allow a vertex to be matched to several others at once, it becomes a generalized assignment problem. There is also priority matching, where certain prioritized vertices are matched before others.

Finally, the complexity of these problems can change drastically depending on the structure of the graph. While bipartite graphs are manageable, finding a maximum-cardinality matching in hypergraphs is much harder. A hypergraph is a generalization where an edge can connect more than two vertices. Even for 3-uniform hypergraphs, where every edge connects exactly three vertices, the problem is NP-complete. This means there is no known way to solve it quickly for all cases. This shows how a small change in the rules of a graph can change the entire difficulty of the puzzle.