Maximally matchable edge
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.
Motivation
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 iff 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]
Definition
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.
Algorithms for general graphs
Currently, the best known deterministic algorithm for general graphs runs in time .[4]
There is a randomized algorithm for general graphs in time .[5]
Algorithms for bipartite graphs
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 .
Bipartite graphs with a perfect matching
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:
- If e is in an alternating cycle, then either e is in M, or - by inverting the cycle - we get a new perfect matching that contains e. Hence, e is maximally-matchable.
- Conversely, if e is maximally-matchable, then it is in some perfect matching N. By taking the symmetric difference of M and N, we can construct an alternating cycle that contains e.
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 componentsin linear time Therefore, the set of all maximally-matchable edges can be found as follows:
- Given the undirected bipartite graph and the perfect matching M, mark every edge in M as maximally-matchable.
- Construct the directed graph as above.
- Find all strongly-connected components in H.
- For each i, j such that are in the same component, mark the edge as maximally-matchable.
- Mark all remaining edges as not maximally-matchable.
Bipartite graphs without a perfect matching
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:
- Edges with both endpoints saturated by M. We call such edges M-upper.
- Edges with exactly one endpoint saturated by M. We call such edges M-lower.
- Note that there are no edges with both endpoints unsaturated by M, since this would contradict the maximality of M.
Theorem: All M-lower edges are maximally-matchable.[1]: sub.2.2 Proof: suppose e = (xi,yj) where xi is saturated and yj is not. Then, removing (xi,yi) from M and adding (xi,yj) 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.
References
- ^ a b c d e f Tassa, Tamir (2012-03-16). "Finding all maximally-matchable edges in a bipartite graph". Theoretical Computer Science. 423: 50–58. doi:10.1016/j.tcs.2011.12.071. ISSN 0304-3975.
- ^ Carvalho, Marcelo H. De; cheriyan, joseph (2005-10-01). "An O(VE) algorithm for ear decompositions of matching-covered graphs". ACM Transactions on Algorithms. 1 (2): 324–337. doi:10.1145/1103963.1103969. ISSN 1549-6325.
- ^ Lovász, László; Plummer, Michael (2009-08-18). Matching Theory. Providence, Rhode Island: American Mathematical Society. doi:10.1090/chel/367. ISBN 9780821847596.
- ^ de Carvalho, Marcelo H.; Cheriyan, Joseph (2005), "An algorithm for ear decompositions of matching-covered graphs", Proc. ACM/SIAM Symposium on Discrete Algorithms (SODA), pp. 415–423.
- ^ Rabin, Michael O.; Vazirani, Vijay V. (1989), "Maximum matchings in general graphs through randomization" (PDF), Journal of Algorithms, 10 (4): 557–567, doi:10.1016/0196-6774(89)90005-9.