Maximum matching by Edmonds

Abstract view

Algo

Type of algorithm: recursion

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.

Induction basis

Abstract view: Start with some matching, for example, the empty matching.

Induction step

Abstract view:

1. Apply the modified repeated graph search from the classical algorithm for the restriction to bipartite graphs.
2. However, in addition:
   1. The search maintains a boolean flag even/odd, which indicates the parity of the distance of the current node from the start node of the current search.
   2. Also, each node has a boolean label even/odd. Whenever this node is seen (not only the first time when it is seen), its label is set according to the flag.
3. If a labeled node is seen again, but with another distance parity than before:
   1. The repeated graph search is terminated.
   2. A blossom [math]\displaystyle{ B }[/math] is identified.
   3. [math]\displaystyle{ C }[/math] is shrunken, giving [math]\displaystyle{ G'=(V',E') }[/math] and the restriction [math]\displaystyle{ M' }[/math] of [math]\displaystyle{ M }[/math] to [math]\displaystyle{ G' }[/math].
   4. The procedure is called recursively with [math]\displaystyle{ G' }[/math] and [math]\displaystyle{ M' }[/math].
   5. Exactly one node of [math]\displaystyle{ C }[/math] is matched by [math]\displaystyle{ M' }[/math], so extend [math]\displaystyle{ M' }[/math] in the obvious, unique way by [math]\displaystyle{ \lfloor|C|/2\rfloor }[/math] edges of [math]\displaystyle{ C }[/math].
   6. Return this extension of [math]\displaystyle{ M' }[/math].

Remark: In typical formulations of this algorithm, the graph search is not left open but the search strategy applied in Hopcroft-Karp is hard-coded.

Implementation of step 3.2:

Proof: Basically, we have to show that