Maximally-matchable edge

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 ${\displaystyle G=(X+Y,E)}$, where ${\displaystyle X=(x_{1},\ldots ,x_{n})}$ and ${\displaystyle Y=(y_{1},\ldots ,y_{n})}$. Let the perfect matching be ${\displaystyle 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 ${\displaystyle H=(Z,E)}$, where ${\displaystyle Z=(z_{1},\ldots ,z_{n})}$ and there is an edge from ${\displaystyle z_{i}}$ to ${\displaystyle z_{j}}$ in H iff ${\displaystyle i\neq j}$ and there is an edge between ${\displaystyle x_{i}}$ and ${\displaystyle 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 componentsin linear time Therefore, the set of all maximally-matchable edges can be found as follows:

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

Let the bipartite graph be ${\displaystyle G=(X+Y,E)}$, where ${\displaystyle X=(x_{1},\ldots ,x_{n})}$ and ${\displaystyle Y=(y_{1},\ldots ,y_{n'})}$ and ${\displaystyle n\leq n'}$. Let the given maximum matching be ${\displaystyle M=\{(x_{1},y_{1}),\ldots ,(x_{t},y_{t})\}}$, where ${\displaystyle 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.[1]^:sub.2.2 Proof: suppose e = (x_i,y_j) where x_i is saturated and y_j is not. Then, removing (x_i,y_i) from M and adding (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[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.