Maximum-cardinality matching
A matching with the largest possible number of edges in a graph.
Maximum-cardinality matching is a fundamental concept in graph theory, referring to a matching—a subgraph where no two edges share a vertex—that contains the largest possible number of edges. This problem arises in many computational contexts, from network flow to assignment tasks, and has spurred the development of numerous algorithms for both bipartite and general graphs.
- field
- Graph theory, computational graph theory
- known_for
- Maximum-cardinality matching, perfect matching, bipartite matching algorithms
- related_algorithms
- Ford–Fulkerson algorithm, Hopcroft–Karp algorithm, blossom algorithm, Micali–Vazirani algorithm
Lore & Background
In graph theory, a maximum-cardinality matching is a subgraph where no two edges share a vertex, and its cardinality is the largest number of edges any matching can contain. For finite graphs, such a matching always exists but is not usually unique. The cardinality is never more than half the number of vertices nor more than the number of edges. If all vertices are covered, it is called a perfect matching. The problem is especially important for bipartite graphs, which represent binary relations with vertices partitioned into left and right sets, as simpler algorithms exist for this case.
Reader's Guide
The computation of maximum-cardinality matchings is a fundamental task in computational graph theory. For bipartite graphs, the Ford–Fulkerson algorithm provides a simple flow-based approach, running in O(VE) time by converting the graph into a flow network. The Hopcroft–Karp algorithm improves this to O(√V E) by searching for multiple augmenting paths simultaneously. More advanced algorithms, such as those by Chandran and Hochbaum, offer running times dependent on the size of the maximum matching. For arbitrary graphs, the blossom algorithm runs in O(|V|²·|E|), while the Micali–Vazirani algorithm achieves O(√V E) for general graphs. These algorithms have applications in deciding the existence of perfect matchings, and generalizations include maximum-weight matching and the assignment problem. The problem becomes NP-complete for hypergraphs even in the 3-uniform case.
Did You Know?
- A maximum-cardinality matching always exists for finite graphs but is not usually unique.
- The cardinality of a matching is never more than half the number of vertices and never more than the number of edges.
- The Ford–Fulkerson algorithm can compute a maximum-cardinality matching in bipartite graphs by converting the graph into a flow network with unit capacities.
- The problem of finding a maximum-cardinality matching in hypergraphs is NP-complete even for 3-uniform hypergraphs.
Frequently Asked Questions
Who is Maximum-cardinality matching?
Maximum-cardinality matching is a foundational concept in graph theory that designates the largest possible collection of edges in a graph where no two edges share a vertex. It is the central problem that a whole family of matching algorithms is built to solve.
What are Maximum-cardinality matching's powers and role?
Its job is to determine the greatest number of mutually non-adjacent edges that can be selected from a given graph, which maps directly onto real-world assignment and network-flow tasks. It powers landmark procedures such as the Hopcroft–Karp algorithm for bipartite graphs and the blossom algorithm for general graphs.
How does Maximum-cardinality matching's story end?
The narrative resolves the moment an algorithm proves that no further edge can be added to the current set without violating the no-shared-vertex constraint. At that certification step, the matching is confirmed to be of maximum possible size.
Why is Maximum-cardinality matching important?
It underlies high-impact applications like pairing workers to jobs and routing traffic through networks, making it one of the most practically consequential problems in computational graph theory. Its study has also driven the invention of celebrated algorithms including Ford–Fulkerson and Micali–Vazirani.
Who are Maximum-cardinality matching's closest allies?
Its most well-known companions are the Hopcroft–Karp algorithm for bipartite settings, the blossom algorithm for general graphs, and the Micali–Vazirani algorithm, each offering different speed-and-complexity trade-offs. The Ford–Fulkerson method also connects to it through the broader network-flow framework.
More in Algorithms And Data Structures 25-38
Elsewhere in the Algorithms And Data Structures universe
Spotted an error? Know more?
This is a living reference — every entry is fact-audited, and reader corrections feed straight into our audit queue. Suggest an edit · See this site's audit record