Hopcroft-Karp

Abstract view

Algorithmic problem: Cardinality-maximal matching in bipartite graphs.

Type of algorithm: loop.

Auxiliary data structures: a set [math]\displaystyle{ S }[/math] of BFS runs as iterators (cf. the corresponding remark). The modification to find augmenting paths is applied.

Invariant:

1. [math]\displaystyle{ M }[/math] is a matching in [math]\displaystyle{ G }[/math].

Variant: The shortest length of an augmenting path in terms of the number of edges is increased.

Break condition: [math]\displaystyle{ S=\emptyset }[/math].

Induction basis

Abstract view:

1. Start with an arbitrary matching, for example, the empty matching.
2. Create and initialize one BFS run for each exposed node.

Induction step

Abstract view: In the [math]\displaystyle{ i }[/math]-th iteration:

1. Process all nodes of distance [math]\displaystyle{ i-1 }[/math] in the queues of all BFS runs.
2. For each BFS run: If it had no nodes to process in step 1, remove it from [math]\displaystyle{ S }[/math].
3. While there are two BFS runs in [math]\displaystyle{ S }[/math] that have seen the same edge:
   1. Choose two such BFS runs and such an edge [math]\displaystyle{ \{v,w\} }[/math], say.
   2. Augment [math]\displaystyle{ M }[/math] along the concatenation of the paths in the two arborescence from the start nodes to [math]\displaystyle{ v }[/math] and [math]\displaystyle{ w }[/math], respectively, and of [math]\displaystyle{ \{v,w\} }[/math].
   3. Remove these two BFS runs from the set of all BFS runs.

Proof: The variant is obviously maintained. To prove the variant, first note