Maximum-cardinality matching

Imagine you have many dots and lines.

Each line joins two dots. We want to pick the most lines. But each dot can only have one line. This is a big puzzle for computers.

Some dots are in two groups. One group is on the left. The other group is on the right. Lines only go from left to right. Computers can solve this very fast.

We can also find a perfect match. This means every dot has a partner. It is a way to group things well.

Imagine you have many dots and lines.

Each line joins two dots. This is called a graph. We want to pick as many lines as we can. But there is a rule. Each dot can only have one line. This task is called maximum-cardinality matching. It means finding the largest group of lines that follow the rule.

Some graphs are special. They are bipartite graphs. In these, dots sit in two groups. Lines only go from the left group to the right group. Computers can solve these very fast. One way is the Ford-Fulkerson algorithm. This method uses a flow network. It treats the lines like water flowing through pipes. Another way is the Hopcroft-Karp algorithm. It is even faster because it looks for many paths at once.

Other graphs are not bipartite. These are general graphs. For these, we use the blossom algorithm. There are also very complex ways to solve them. Finding a perfect matching is one goal. This means every single dot has a partner. This math helps us solve many grouping puzzles.

Imagine you have a collection of dots and lines.

In math, we call this a graph. Each line connects two dots. A matching is a set of lines where no two lines share a dot. This means every dot is connected to at most one line. The goal of maximum-cardinality matching is to find the largest possible group of these lines. This helps us find how many pairs we can make. It is a very important puzzle in the study of computers and graphs.

Some graphs are easier to solve than others. A bipartite graph is a special kind of graph. In these graphs, dots are split into two separate groups. Lines only connect a dot from the left group to one on the right. We can solve these using a flow-based algorithm. The Ford–Fulkerson algorithm is one simple way to do this. It treats the graph like a network where things flow through paths. Another way is the Hopcroft–Karp algorithm. This method is faster because it searches for many paths at the same time.

Math experts have found many ways to solve these problems. For bipartite graphs, the Hopcroft–Karp algorithm is a very famous tool. There is also an algorithm by Chandran and Hochbaum. This one is useful because its speed depends on the size of the matching. For certain types of graphs, we have even faster methods. Madry's algorithm works well for sparse bipartite graphs using electric flows. For planar bipartite graphs, we can use a different method to find the matching quickly.

General graphs are harder because they do not have two neat groups. For these, we use the blossom algorithm. This algorithm finds the largest matching in a general graph. A much more complicated method was made by Micali and Vazirani. This method is very fast and matches the speed of the Hopcroft–Karp algorithm. Other researchers like Gabow and Tarjan also found ways to reach this speed. There is even a way to use randomness to solve these puzzles. This uses a fast matrix multiplication method to find answers.

Finding a maximum matching can tell us many things. It can show us if a perfect matching exists. A perfect matching is when every single dot has a partner. We can also look at weighted graphs. This is called the maximum-weight matching problem. If we want to match dots to many others, it is a generalized assignment problem. Sometimes, we might even have a priority matching. This is when we match certain important dots first. These ideas help us solve many real grouping puzzles.

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.