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 ${\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 components in 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.

Bipartite graphs without a perfect matching

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 ${\displaystyle M}$-lower edges are maximally matchable.^{[1]: sub.2.2} Proof: suppose ${\displaystyle e=(x_{i},y_{j})}$ where ${\displaystyle x_{i}}$ is saturated and ${\displaystyle y_{i}}$ is not. Then, removing ${\displaystyle e=(x_{i},y_{j})}$ from ${\displaystyle M}$ and adding ${\displaystyle 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^[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.