HOME

TheInfoList



OR:

Maximum cardinality matching is a fundamental problem in
graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
. We are given a
graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...
, and the goal is to find a matching containing as many edges as possible; that is, a maximum
cardinality In mathematics, the cardinality of a set is a measure of the number of elements of the set. For example, the set A = \ contains 3 elements, and therefore A has a cardinality of 3. Beginning in the late 19th century, this concept was generalized ...
subset of the edges such that each
vertex Vertex, vertices or vertexes may refer to: Science and technology Mathematics and computer science *Vertex (geometry), a point where two or more curves, lines, or edges meet *Vertex (computer graphics), a data structure that describes the position ...
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 In logic, especially as applied in mathematics, concept is a special case or specialization of concept precisely if every instance of is also an instance of but not vice versa, or equivalently, if is a generalization of . A limiting case ...
of the maximum cardinality matching problem is when is a
bipartite graph In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V a ...
, whose vertices are partitioned between left vertices in and right vertices in , and edges in 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 can be converted to a
flow network In graph theory, a flow network (also known as a transportation network) is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Often in operations re ...
as follows. * Add a source vertex ; add an edge from to each vertex in . * Add a sink vertex ; add an edge from each vertex in to . * 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 is at most 1, so the outgoing flow is at most 1 too, so at most one edge adjacent to each vertex in is present. * The outgoing flow from each vertex in is at most 1, so the incoming flow is at most 1 too, so at most one edge adjacent to each vertex in is present. The Ford–Fulkerson algorithm proceeds by repeatedly finding an augmenting path from some to some and updating the matching by taking the symmetric difference of that path with (assuming such a path exists). As each path can be found in time, the running time is , and the maximum matching consists of the edges of that carry flow from to .


Advanced algorithms

An improvement to this algorithm is given by the more elaborate
Hopcroft–Karp algorithm In computer science, the Hopcroft–Karp algorithm (sometimes more accurately called the Hopcroft–Karp–Karzanov algorithm) is an algorithm that takes a bipartite graph as input and produces a maximum cardinality matching as output – a set of ...
, which searches for multiple augmenting paths simultaneously. This algorithm runs in O(\sqrtE) time. The algorithm of Chandran and Hochbaum for bipartite graphs runs in time that depends on the size of the maximum matching , which for is :O\left(\min\+ \sqrt \min \\right). Using boolean operations on words of size \lambda the complexity is further improved to :O\left(\min \left\ + k^2 + \frac\right). More efficient algorithms exist for special kinds of bipartite graphs: * For sparse bipartite graphs, the maximum matching problem can be solved in \tilde(E^) with Madry's algorithm based on electric flows. * For planar bipartite graphs, the problem can be solved in time where is the number of vertices, by reducing the problem to
maximum flow In optimization theory, maximum flow problems involve finding a feasible flow through a flow network that obtains the maximum possible flow rate. The maximum flow problem can be seen as a special case of more complex network flow problems, such ...
with multiple sources and sinks.


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 for general graphs, matching the performance of the
Hopcroft–Karp algorithm In computer science, the Hopcroft–Karp algorithm (sometimes more accurately called the Hopcroft–Karp–Karzanov algorithm) is an algorithm that takes a bipartite graph as input and produces a maximum cardinality matching as output – a set of ...
on bipartite graphs, can be achieved with the much more complicated algorithm of Micali and Vazirani. The same bound was achieved by an algorithm by Blum ( de) and an algorithm by Gabow and Tarjan. An alternative approach uses
randomization Randomization is the process of making something random. Randomization is not haphazard; instead, a random process is a sequence of random variables describing a process whose outcomes do not follow a deterministic pattern, but follow an evolution d ...
and is based on the fast
matrix multiplication In mathematics, particularly in linear algebra, matrix multiplication is a binary operation that produces a matrix from two matrices. For matrix multiplication, the number of columns in the first matrix must be equal to the number of rows in the s ...
algorithm. This gives a randomized algorithm for general graphs with complexity O(V^). This is better in theory for sufficiently
dense graph In mathematics, a dense graph is a graph in which the number of edges is close to the maximal number of edges (where every pair of vertices is connected by one edge). The opposite, a graph with only a few edges, is a sparse graph. The distincti ...
s, but in practice the algorithm is slower.. Other algorithms for the task are reviewed by Duan and Pettie (see Table I). In terms of
approximation algorithm In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned sol ...
s, they also point out that the blossom algorithm and the algorithms by Micali and Vazirani can be seen as
approximation algorithm In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned sol ...
s 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 In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph , a perfect matching in is a subset of edge set , such that every vertex in the vertex set is adjacent to exactl ...
. * The problem of finding a matching with maximum weight in a
weighted graph This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges. Symbols A B ...
is called the maximum weight matching problem, and its restriction to bipartite graphs is called the
assignment problem The assignment problem is a fundamental combinatorial optimization problem. In its most general form, the problem is as follows: :The problem instance has a number of ''agents'' and a number of ''tasks''. Any agent can be assigned to perform any ta ...
. If each vertex can be matched to several vertices at once, then this is a generalized assignment problem. * A
priority matching In graph theory, a priority matching (also called: maximum priority matching) is a matching that maximizes the number of high-priority vertices that participate in the matching. Formally, we are given a graph , and a partition of the vertex-set ...
is a particular maximum-cardinality matching in which prioritized vertices are matched first. * The problem of finding a maximum-cardinality matching in a hypergraph is NP-complete even for 3-uniform hypergraphs.


References

{{Reflist Matching (graph theory)