Maximum matching by Edmonds
Abstract view
Invariant: The current selection [math]\displaystyle{ M }[/math] of edges is a matching.
Variant: Either the cardinality of [math]\displaystyle{ M }[/math] increases, or the number of nodes of [math]\displaystyle{ G }[/math] decreases.
Break condition: There is no more augmenting path.
Definition: A blossom is a cycle [math]\displaystyle{ C }[/math] of odd lengths in [math]\displaystyle{ G }[/math] such that [math]\displaystyle{ \lfloor|C|/2\rfloor }[/math] edges on [math]\displaystyle{ C }[/math] are matched and the remaining node is matched as well (by an edge not on [math]\displaystyle{ C }[/math], in fact).
Induction basis
Abstract view: Start with some matching, for example, the empty matching.
Induction step
Abstract view:
- Apply the modified graph search from the classical algorithm for the restriction to bipartite graphs.
- However, in addition, each node has a boolean label even/odd, which is set when the graph search sees the node for the very first time. More specifically, for each node this is the parity of the distance from the start node in the arborescence.
Implementation of step 1: