Algorithms for general graphs
Currently, the best known deterministic algorithm for general graphs runs in time . [2]
There is a randomized algorithm for general graphs in time . [4]
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. [1] An alternative term is allowed edge. [2] [3]
A fundamental problem in matching theory is: given a graph G, find the set of all maximally matchable edges in G. This is equivalent to finding the union of all maximum matchings in G (this is different than the simpler problem of finding a single maximum matching in G). Several algorithms for this problem are known.
Consider a matchmaking agency with a pool of men and women. Given the preferences of the candidates, the agency constructs a bipartite graph where there is an edge between a man and a woman if they are compatible. The ultimate goal of the agency is to create as many compatible couples as possible, i.e., find a maximum-cardinality matching in this graph. Towards this goal, the agency first chooses an edge in the graph, and suggests to the man and woman on both ends of the edge to meet. Now, the agency must take care to only choose a maximally matchable edge. This is because, if it chooses a non-maximally matchable edge, it may get stuck with an edge that cannot be completed to a maximum-cardinality matching. [1]
Let G = (V,E) be a graph, where V are the vertices and E are the edges. A matching in G is a subset M of E, such that each vertex in V is adjacent to at most a single edge in M. A maximum matching is a matching of maximum cardinality.
An edge e in E is called maximally matchable (or allowed) if there exists a maximum matching M that contains e.
Currently, the best known deterministic algorithm for general graphs runs in time . [2]
There is a randomized algorithm for general graphs in time . [4]
In bipartite graphs, if a single maximum-cardinality matching is known, it is possible to find all maximally matchable edges in linear time - . [1]
If a maximum matching is not known, it can be found by existing algorithms. In this case, the resulting overall runtime is for general bipartite graphs and for dense bipartite graphs with .
The algorithm for finding maximally matchable edges is simpler when the graph admits a perfect matching. [1] : sub.2.1
Let the bipartite graph be , where and . Let the perfect matching be .
Theorem: an edge e is maximally matchable if-and-only-if e is included in some M-alternating cycle - a cycle that alternates between edges in M and edges not in M. Proof:
Now, consider a directed graph , where and there is an edge from to in H iff and there is an edge between and in G (note that by assumption such edges are not in M). Each M-alternating cycle in G corresponds to a directed cycle in H. A directed edge belongs to a directed cycle iff both its endpoints belong to the same strongly connected component. There are algorithms for finding all strongly connected components in linear time. Therefore, the set of all maximally matchable edges can be found as follows:
Let the bipartite graph be , where and and . Let the given maximum matching be , where . The edges in E can be categorized into two classes:
Theorem: All -lower edges are maximally matchable. [1] : sub.2.2 Proof: suppose where is saturated and is not. Then, removing from and adding yields a new maximum-cardinality matching.
Hence, it remains to find the maximally matchable edges among the M-upper ones.
Let H be the subgraph of G induced by the M-saturated nodes. Note that M is a perfect matching in H. Hence, using the algorithm of the previous subsection, it is possible to find all edges that are maximally matchable in H. Tassa [1] explains how to find the remaining maximally matchable edges, as well as how to dynamically update the set of maximally matchable edges when the graph changes.
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.
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.
In optimization theory, maximum flow problems involve finding a feasible flow through a flow network that obtains the maximum possible flow rate.
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 perfect graph is a graph in which the chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic number is greater than or equal to the size of the maximum clique, but they can be far apart. A graph is perfect when these numbers are equal, and remain equal after the deletion of arbitrary subsets of vertices.
In mathematics, in the areas of order theory and combinatorics, Dilworth's theorem characterizes the width of any finite partially ordered set in terms of a partition of the order into a minimum number of chains. It is named for the mathematician Robert P. Dilworth (1950).
In graph theory, a maximal independent set (MIS) or maximal stable set is an independent set that is not a subset of any other independent set. In other words, there is no vertex outside the independent set that may join it because it is maximal with respect to the independent set property.
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 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.
Maximum cardinality matching is a fundamental problem in graph theory. 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.
In combinatorial optimization, the matroid intersection problem is to find a largest common independent set in two matroids over the same ground set. If the elements of the matroid are assigned real weights, the weighted matroid intersection problem is to find a common independent set with the maximum possible weight. These problems generalize many problems in combinatorial optimization including finding maximum matchings and maximum weight matchings in bipartite graphs and finding arborescences in directed graphs.
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 graph theory, a well-covered graph is an undirected graph in which every minimal vertex cover has the same size as every other minimal vertex cover. Equivalently, these are the graphs in which all maximal independent sets have equal size. Well-covered graphs were defined and first studied by Michael D. Plummer in 1970.
Rank-maximal (RM) allocation is a rule for fair division of indivisible items. Suppose we have to allocate some items among people. Each person can rank the items from best to worst. The RM rule says that we have to give as many people as possible their best (#1) item. Subject to that, we have to give as many people as possible their next-best (#2) item, and so on.
In the mathematical field of graph theory, Hall-type theorems for hypergraphs are several generalizations of Hall's marriage theorem from graphs to hypergraphs. Such theorems were proved by Ofra Kessler, Ron Aharoni, Penny Haxell, Roy Meshulam, and others.
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.
