• • In bipartite graphs, if a single
maximum-cardinality matching is known, it is possible to find all maximally matchable edges in linear time - O(V+E). If a maximum matching is not known, it can be found by existing algorithms. In this case, the resulting overall runtime is O(V^{1/2}E) for general bipartite graphs and O((V/\log V)^{1/2}E) for dense bipartite graphs with E=\Theta(V^2).
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 G=(X+Y, E), where X = (x_1,\ldots,x_n) and Y=(y_1,\ldots,y_n). Let the perfect matching be M = \{(x_1,y_1),\ldots,(x_n,y_n)\}.
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 H=(Z, E), where Z = (z_1,\ldots,z_n) and there is an edge from z_i to z_j in
H iff i\neq j and there is an edge between x_i and y_j 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 G=(X+Y, E) and the perfect matching
M, mark every edge
(x_i,y_i) in
M as maximally matchable. • Construct the directed graph H=(Z, E) as above. • Find all strongly connected components in
H. • For each
i,
j such that
(z_i,z_j) are in the same component, mark the edge
(x_i,y_j) as maximally matchable. • Mark all remaining edges as not maximally matchable.
Bipartite graphs without a perfect matching Let the bipartite graph be G=(X+Y, E), where X = (x_1,\ldots,x_n) and Y=(y_1,\ldots,y_{n'}) and n\leq n'. Let the given maximum matching be M = \{(x_1,y_1),\ldots,(x_t,y_t)\}, where t \leq n \leq n'. 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.
Proof: suppose e = (x_i,y_j) where x_i is saturated and y_i is not. Then, removing e = (x_i,y_j) from M and adding e = (x_i,y_j) 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. == References ==