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. An alternative term is allowed edge. 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 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.

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 [math]\displaystyle{ O(VE) }[/math] .

There is a randomized algorithm for general graphs in time [math]\displaystyle{ \tilde{O}(V^{2.376}) }[/math] .

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 - [math]\displaystyle{ O(V+E) }[/math].

If a maximum matching is not known, it can be found by existing algorithms. In this case, the resulting overall runtime is [math]\displaystyle{ O(V^{1/2}E) }[/math] for general bipartite graphs and [math]\displaystyle{ O((V/\log V)^{1/2}E) }[/math] for dense bipartite graphs with [math]\displaystyle{ E=\Theta(V^2) }[/math].

Bipartite graphs with a perfect matching

The algorithm for finding maximally-matchable edges is simpler when the graph admits a perfect matching.

Let the bipartite graph be [math]\displaystyle{ G=(X+Y, E) }[/math], where [math]\displaystyle{ X = (x_1,\ldots,x_n) }[/math] and [math]\displaystyle{ Y=(y_1,\ldots,y_n) }[/math]. Let the perfect matching be [math]\displaystyle{ M = \{(x_1,y_1),\ldots,(x_n,y_n)\} }[/math].

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 [math]\displaystyle{ H=(Z, E) }[/math], where [math]\displaystyle{ Z = (z_1,\ldots,z_n) }[/math] and there is an edge from [math]\displaystyle{ z_i }[/math] to [math]\displaystyle{ z_j }[/math] in H iff [math]\displaystyle{ i\neq j }[/math] and there is an edge between [math]\displaystyle{ x_i }[/math] and [math]\displaystyle{ y_j }[/math] 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:

• Given the undirected bipartite graph [math]\displaystyle{ G=(X+Y, E) }[/math] and the perfect matching M, mark every edge [math]\displaystyle{ (x_i,y_i) }[/math] in M as maximally-matchable.
• Construct the directed graph [math]\displaystyle{ H=(Z, E) }[/math] as above.
• Find all strongly-connected components in H.
• For each i, j such that [math]\displaystyle{ (z_i,z_j) }[/math] are in the same component, mark the edge [math]\displaystyle{ (x_i,y_j) }[/math] as maximally-matchable.
• Mark all remaining edges as not maximally-matchable.

Bipartite graphs without a perfect matching

Let the bipartite graph be [math]\displaystyle{ G=(X+Y, E) }[/math], where [math]\displaystyle{ X = (x_1,\ldots,x_n) }[/math] and [math]\displaystyle{ Y=(y_1,\ldots,y_{n'}) }[/math] and [math]\displaystyle{ n\leq n' }[/math]. Let the given maximum matching be [math]\displaystyle{ M = \{(x_1,y_1),\ldots,(x_t,y_t)\} }[/math], where [math]\displaystyle{ t \leq n \leq n' }[/math]. 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 [math]\displaystyle{ M }[/math]-lower edges are maximally-matchable. Proof: suppose [math]\displaystyle{ e = (x_i,y_j) }[/math] where [math]\displaystyle{ x_i }[/math] is saturated and [math]\displaystyle{ y_i }[/math] is not. Then, removing [math]\displaystyle{ e = (x_i,y_j) }[/math] from [math]\displaystyle{ M }[/math] and adding [math]\displaystyle{ e = (x_i,y_j) }[/math] 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 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.