Maximum-cardinality matching

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. The cardinality of a matching is simply the count of its edges, and the maximum cardinality is the greatest such count achievable for a given graph. A matching is considered maximum-cardinality when it attains this upper bound. This can be visualized as the largest possible non-overlapping cover of the graph’s vertices, where each edge is thought of as covering its two endpoints exactly once. If every vertex in the graph is covered, the matching is termed perfect. For any finite graph, such a maximum matching always exists, though it is rarely unique. The cardinality of any matching is inherently limited: it can never exceed half the number of vertices, nor can it surpass the total number of edges. A key special case arises when the graph is bipartite, meaning its vertices can be split into two sets with edges only connecting across the sets. In this bipartite scenario, the problem can be solved with simpler, more efficient algorithms than those required for general graphs. The computation of a maximum matching is a core task in computational graph theory, and while there are nonconstructive theorems characterizing the size of such a matching, the focus of this topic is on algorithmic computation. For bipartite graphs, a straightforward method converts the graph into a flow network by adding a source and sink with unit-capacity edges, then applies the Ford–Fulkerson algorithm to find a maximum flow, which directly yields a maximum matching. More advanced approaches, such as the Hopcroft–Karp algorithm, improve efficiency by searching for multiple augmenting paths simultaneously. For arbitrary, non-bipartite graphs, the blossom algorithm provides a solution, with further refinements achieving performance comparable to bipartite-specific methods. Randomized algorithms based on fast matrix multiplication offer theoretical advantages for dense graphs, though they are slower in practice. The problem also has important applications, including determining the existence of a perfect matching, and generalizations to weighted graphs (the maximum-weight matching problem) and hypergraphs, where the latter becomes NP-complete for certain cases.