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: Before and after each iteration:

1. [math]\displaystyle{ M }[/math] is a matching in [math]\displaystyle{ G }[/math].
2. All exposed nodes that are end nodes of augmenting paths, are in [math]\displaystyle{ S }[/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 arborescences of these two BFS runs 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, consider an execution of step 3.2. Let [math]\displaystyle{ p }[/math] denote the path along which the augmentation takes place. Let [math]\displaystyle{ p' }[/math] and [math]\displaystyle{ p'' }[/math] the paths in he arborescences from the start nodes to [math]\displaystyle{ v }[/math] and [math]\displaystyle{ w }[/math], respectively.

For a contradiction, suppose augmenting along [math]\displaystyle{ p }[/math] has created a a new augmenting path [math]\displaystyle{ q }[/math] that is not longer than [math]\displaystyle{ p }[/math]. In either orientation of [math]\displaystyle{ p }[/math] and [math]\displaystyle{ q }[/math], let [math]\displaystyle{ v' }[/math] be the first node of [math]\displaystyle{ p }[/math] that also belongs to [math]\displaystyle{ q }[/math], and let [math]\displaystyle{ w' }[/math] be the last node of [math]\displaystyle{ p }[/math] that also belongs to [math]\displaystyle{ q }[/math]. Without loss of generality, let [math]\displaystyle{ v }[/math] be the last node of [math]\displaystyle{ p' }[/math] and let [math]\displaystyle{ v }[/math] be on [math]\displaystyle{ p' }[/math]. Note that each edge of [math]\displaystyle{ q }[/math] that is incident to exactly one node on [math]\displaystyle{ p }[/math] must be unmatched.

First, [math]\displaystyle{ v'=v }[/math] must hold because, otherwise, one subpath of [math]\displaystyle{ p }[/math] up to [math]\displaystyle{ v' }[/math] and one of [math]\displaystyle{ q }[/math] up to [math]\displaystyle{ v' }[/math] would be a shorter augmenting path, which contradicts the induction hypothesis. Moreover, [math]\displaystyle{ v'=v }[/math] implies that [math]\displaystyle{ w }[/math] must belong to [math]\displaystyle{ p'' }[/math] and, by the same argument, [math]\displaystyle{ w'=w }[/math] must hold. So, the intersection of [math]\displaystyle{ p }[/math] and [math]\displaystyle{ q }[/math] is exactly [math]\displaystyle{ \{v,w\} }[/math]. Therefore, after the augmentation along [math]\displaystyle{ p }[/math], [math]\displaystyle{ q }[/math] becomes a candidate. Augmenting along [math]\displaystyle{ q }[/math] does not generate new augmenting paths because these new paths would intersect with [math]\displaystyle{ q }[/math] exactly on [math]\displaystyle{ \{v,w\} }[/math] for the same reason, but [math]\displaystyle{ \{v,w\} }[/math] is not matched anymore, and the two incident edges on this assumed new path are not matched, either, so this assumed new path is not alternating.

Correctness

Due to the invariant, the matching is cardinality-maximal if the main loop terminates. termination of the main loop results from the following complexity considerations.