Maximum cardinality matching

Last updated October 01, 2023

Maximum cardinality matching is a fundamental problem in graph theory.^[1] We are given a graph $G$ , 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 $G$ is a bipartite graph, whose vertices $V$ are partitioned between left vertices in $X$ and right vertices in $Y$ , and edges in $E$ 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 $(X + Y, E)$ can be converted to a flow network as follows.

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

The Ford–Fulkerson algorithm proceeds by repeatedly finding an augmenting path from some $x \in X$ to some $y \in Y$ and updating the matching $M$ by taking the symmetric difference of that path with $M$ (assuming such a path exists). As each path can be found in $O (E)$ time, the running time is $O (VE)$ , and the maximum matching consists of the edges of $E$ that carry flow from $X$ to $Y$ .

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^[2] for bipartite graphs runs in time that depends on the size of the maximum matching $k$ , which for $| X | < | Y |$ is

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

Using boolean operations on words of size $\lambda$ the complexity is further improved to^[2]

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

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.^[3]
For planar bipartite graphs, the problem can be solved in time $O (n log 3 n)$ where $n$ is the number of vertices, by reducing the problem to maximum flow with multiple sources and sinks.^[4]

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 $O (\sqrt V E)$ 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.^[5] The same bound was achieved by an algorithm by Blum (de)^[6] and an algorithm by Gabow and Tarjan.^[7]

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.376})$ .^[8] This is better in theory for sufficiently dense graphs, but in practice the algorithm is slower.^[2]

Other algorithms for the task are reviewed by Duan and Pettie^[9] (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.^[10]

Related Research Articles

In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph $G = (V, E)$ , a perfect matching in $G$ is a subset $M$ of edge set $E$ , such that every vertex in the vertex set $V$ is adjacent to exactly one edge in $M$ .

The assignment problem is a fundamental combinatorial optimization problem. In its most general form, the problem is as follows:

In mathematics, Hall's marriage theorem, proved by Philip Hall (1935), is a theorem with two equivalent formulations. In each case, the theorem gives a necessary and sufficient condition for an object to exist:

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets $and, that is, every edge connects a vertex in to one in . Vertex sets and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.$

In optimization theory, maximum flow problems involve finding a feasible flow through a flow network that obtains the maximum possible flow rate.

In graph theory, a vertex cover of a graph is a set of vertices that includes at least one endpoint of every edge of the graph.

In the mathematical discipline of graph theory, a matching or independent edge set in an undirected graph is a set of edges without common vertices. In other words, a subset of the edges is a matching if each vertex appears in at most one edge of that matching. Finding a matching in a bipartite graph can be treated as a network flow problem.

In graph theory, a proper edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most $k$ different colors, for a given value of $k$ , or with the fewest possible colors. The minimum required number of colors for the edges of a given graph is called the chromatic index of the graph. For example, the edges of the graph in the illustration can be colored by three colors but cannot be colored by two colors, so the graph shown has chromatic index three.

<span class="mw-page-title-main">Dominating set</span> Subset of a graphs nodes such that all other nodes link to at least one

In graph theory, a dominating set for a graph $G$ is a subset $D$ of its vertices, such that any vertex of $G$ is either in $D$ , or has a neighbor in $D$ . The domination number $γ(G)$ is the number of vertices in a smallest dominating set for $G$ .

In graph theory, a cut is a partition of the vertices of a graph into two disjoint subsets. Any cut determines a cut-set, the set of edges that have one endpoint in each subset of the partition. These edges are said to cross the cut. In a connected graph, each cut-set determines a unique cut, and in some cases cuts are identified with their cut-sets rather than with their vertex partitions.

In graph theory, the Dulmage–Mendelsohn decomposition is a partition of the vertices of a bipartite graph into subsets, with the property that two adjacent vertices belong to the same subset if and only if they are paired with each other in a perfect matching of the graph. It is named after A. L. Dulmage and Nathan Mendelsohn, who published it in 1958. A generalization to any graph is the Edmonds–Gallai decomposition, using the Blossom algorithm.

In graph theory, a connected graph is $k$ -edge-connected if it remains connected whenever fewer than $k$ edges are removed.

<span class="mw-page-title-main">Kőnig's theorem (graph theory)</span> Theorem showing that maximum matching and minimum vertex cover are equivalent for bipartite graphs

In the mathematical area of graph theory, Kőnig's theorem, proved by Dénes Kőnig (1931), describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs. It was discovered independently, also in 1931, by Jenő Egerváry in the more general case of weighted graphs.

In computer science, the Hopcroft–Karp algorithm is an algorithm that takes a bipartite graph as input and produces a maximum-cardinality matching as output — a set of as many edges as possible with the property that no two edges share an endpoint. It runs in $time in the worst case, where is set of edges in the graph, is set of vertices of the graph, and it is assumed that . In the case of dense graphs the time bound becomes, and for sparse random graphs it runs in time with high probability.$

The minimum-cost flow problem (MCFP) is an optimization and decision problem to find the cheapest possible way of sending a certain amount of flow through a flow network. A typical application of this problem involves finding the best delivery route from a factory to a warehouse where the road network has some capacity and cost associated. The minimum cost flow problem is one of the most fundamental among all flow and circulation problems because most other such problems can be cast as a minimum cost flow problem and also that it can be solved efficiently using the network simplex algorithm.

In graph theory, the blossom algorithm is an algorithm for constructing maximum matchings on graphs. The algorithm was developed by Jack Edmonds in 1961, and published in 1965. Given a general graph $G = (V, E)$ , the algorithm finds a matching $M$ such that each vertex in $V$ is incident with at most one edge in $M$ and $| M |$ is maximized. The matching is constructed by iteratively improving an initial empty matching along augmenting paths in the graph. Unlike bipartite matching, the key new idea is that an odd-length cycle in the graph (blossom) is contracted to a single vertex, with the search continuing iteratively in the contracted graph.

In mathematics and computer science, graph edit distance (GED) is a measure of similarity between two graphs. The concept of graph edit distance was first formalized mathematically by Alberto Sanfeliu and King-Sun Fu in 1983. A major application of graph edit distance is in inexact graph matching, such as error-tolerant pattern recognition in machine learning.

In graph theory, a Hall violator is a set of vertices in a graph, that violate the condition to Hall's marriage theorem.

In graph theory, a maximally matchable edge in a graph is an edge that is included in at least one maximum-cardinality matching in the graph. An alternative term is allowed edge.

In graph theory, a fractional matching is a generalization of a matching in which, intuitively, each vertex may be broken into fractions that are matched to different neighbor vertices.

References

↑ West, Douglas Brent (1999), Introduction to Graph Theory (2nd ed.), Prentice Hall, Chapter 3, ISBN 0-13-014400-2
1 2 3 Chandran, Bala G.; Hochbaum, Dorit S. (2011), Practical and theoretical improvements for bipartite matching using the pseudoflow algorithm, arXiv: 1105.1569 , Bibcode:2011arXiv1105.1569C, the theoretically efficient algorithms listed above tend to perform poorly in practice.
↑ Madry, A (2013), "Navigating Central Path with Electrical Flows: From Flows to Matchings, and Back", Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on, pp. 253–262, arXiv: 1307.2205 , Bibcode:2013arXiv1307.2205M
↑ Borradaile, Glencora; Klein, Philip N.; Mozes, Shay; Nussbaum, Yahav; Wulff–Nilsen, Christian (2017), "Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time", SIAM Journal on Computing , 46 (4): 1280–1303, arXiv: 1105.2228 , doi:10.1137/15M1042929, MR 3681377, S2CID 207071917
↑ Micali, S.; Vazirani, V. V. (1980), "An $\scriptstyle O({\sqrt {|V|}}\cdot |E|)$ algorithm for finding maximum matching in general graphs", Proc. 21st IEEE Symp. Foundations of Computer Science , pp. 17–27, doi:10.1109/SFCS.1980.12, S2CID 27467816 .
↑ Blum, Norbert (1990). Paterson, Michael S. (ed.). "A new approach to maximum matching in general graphs" (PDF). Automata, Languages and Programming. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer. 443: 586–597. doi:10.1007/BFb0032060. ISBN 978-3-540-47159-2.
↑ Gabow, Harold N; Tarjan, Robert E (1991-10-01). "Faster scaling algorithms for general graph matching problems" (PDF). Journal of the ACM. 38 (4): 815–853. doi:10.1145/115234.115366. S2CID 18350108.
↑ Mucha, M.; Sankowski, P. (2004), "Maximum Matchings via Gaussian Elimination" (PDF), Proc. 45th IEEE Symp. Foundations of Computer Science , pp. 248–255
↑ Duan, Ran; Pettie, Seth (2014-01-01). "Linear-Time Approximation for Maximum Weight Matching" (PDF). Journal of the ACM. 61: 1–23. doi:10.1145/2529989. S2CID 207208641.
↑ Karp, Richard M. (1972), Miller, Raymond E.; Thatcher, James W.; Bohlinger, Jean D. (eds.), "Reducibility among Combinatorial Problems", Complexity of Computer Computations: Proceedings of a symposium on the Complexity of Computer Computations, held March 20–22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, and sponsored by the Office of Naval Research, Mathematics Program, IBM World Trade Corporation, and the IBM Research Mathematical Sciences Department, The IBM Research Symposia Series, Boston, MA: Springer US, pp. 85–103, doi:10.1007/978-1-4684-2001-2_9, ISBN 978-1-4684-2001-2

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[Wes01-1] West, Douglas Brent (1999), Introduction to Graph Theory (2nd ed.), Prentice Hall, Chapter 3, ISBN 0-13-014400-2

[Chandran-2] 1 2 3 Chandran, Bala G.; Hochbaum, Dorit S. (2011), Practical and theoretical improvements for bipartite matching using the pseudoflow algorithm, arXiv: 1105.1569 , Bibcode:2011arXiv1105.1569C, the theoretically efficient algorithms listed above tend to perform poorly in practice.

[3] Madry, A (2013), "Navigating Central Path with Electrical Flows: From Flows to Matchings, and Back", Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on, pp. 253–262, arXiv: 1307.2205 , Bibcode:2013arXiv1307.2205M

[4] Borradaile, Glencora; Klein, Philip N.; Mozes, Shay; Nussbaum, Yahav; Wulff–Nilsen, Christian (2017), "Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time", SIAM Journal on Computing , 46 (4): 1280–1303, arXiv: 1105.2228 , doi:10.1137/15M1042929, MR 3681377, S2CID 207071917

[5] Micali, S.; Vazirani, V. V. (1980), "An $\scriptstyle O({\sqrt {|V|}}\cdot |E|)$ algorithm for finding maximum matching in general graphs", Proc. 21st IEEE Symp. Foundations of Computer Science , pp. 17–27, doi:10.1109/SFCS.1980.12, S2CID 27467816 .

[6] Blum, Norbert (1990). Paterson, Michael S. (ed.). "A new approach to maximum matching in general graphs" (PDF). Automata, Languages and Programming. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer. 443: 586–597. doi:10.1007/BFb0032060. ISBN 978-3-540-47159-2.

[7] Gabow, Harold N; Tarjan, Robert E (1991-10-01). "Faster scaling algorithms for general graph matching problems" (PDF). Journal of the ACM. 38 (4): 815–853. doi:10.1145/115234.115366. S2CID 18350108.

[Mucha-8] Mucha, M.; Sankowski, P. (2004), "Maximum Matchings via Gaussian Elimination" (PDF), Proc. 45th IEEE Symp. Foundations of Computer Science , pp. 248–255

[9] Duan, Ran; Pettie, Seth (2014-01-01). "Linear-Time Approximation for Maximum Weight Matching" (PDF). Journal of the ACM. 61: 1–23. doi:10.1145/2529989. S2CID 207208641.

[10] Karp, Richard M. (1972), Miller, Raymond E.; Thatcher, James W.; Bohlinger, Jean D. (eds.), "Reducibility among Combinatorial Problems", Complexity of Computer Computations: Proceedings of a symposium on the Complexity of Computer Computations, held March 20–22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, and sponsored by the Office of Naval Research, Mathematics Program, IBM World Trade Corporation, and the IBM Research Mathematical Sciences Department, The IBM Research Symposia Series, Boston, MA: Springer US, pp. 85–103, doi:10.1007/978-1-4684-2001-2_9, ISBN 978-1-4684-2001-2

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]