Classical bipartite cardinality matching

Abstract view

Algorithmic problem: Cardinality-maximal matching in bipartite graphs.

Type of algorithm: loop.

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

Variant: [math]\displaystyle{ |M| }[/math] is increased by one.

Break condition: There is no more augmenting path.

Induction basis

Abstract view: Initialize [math]\displaystyle{ M }[/math] to be a feasible matching, for example, the empty matching.

Induction step:

Abstract view:

1. Search for an augmenting path.
2. If there is none, the loop terminates.
3. Let [math]\displaystyle{ p }[/math] denote the augmenting path found in step 1.
4. Augment [math]\displaystyle{ M }[/math] along [math]\displaystyle{ p }[/math].

Implementation of step 1: From every exposed node, a graph traversal algorithm is started that generates an arborescence from the start node (for example, a DFS or a BFS). This repeated graph search is finished once an augmenting path has been found. However, the graph search algorithm is modified as follows:

1. Whenever the current node [math]\displaystyle{ v }[/math] has been reached via an edge in [math]\displaystyle{ M }[/math], only incident edges in [math]\displaystyle{ E\setminus M }[/math] are considered for seeing new nodes.
2. Mirror-symmetrically, whenever the current node [math]\displaystyle{ v }[/math] has been reached via an edge in [math]\displaystyle{ E\setminus M }[/math], only the (unique) incident edge in [math]\displaystyle{ M }[/math], if existing, is considered for seeing a new node.

Proof: Basically, we have to show that there is no more augmenting path if this modified BFS does not find one. So suppose for a contradiction that a search from an exposed node [math]\displaystyle{ u }[/math] fails although there is an augmenting path [math]\displaystyle{ p }[/math] starting in [math]\displaystyle{ u }[/math]. Let [math]\displaystyle{ v }[/math] be the last node on [math]\displaystyle{ p }[/math] such that the subpath [math]\displaystyle{ p' }[/math] of [math]\displaystyle{ p }[/math] from [math]\displaystyle{ u }[/math] to [math]\displaystyle{ v }[/math] belongs to the arborescence generated by the BFS run. Note that [math]\displaystyle{ v\neq u }[/math]. The

Remark: This modified BFS could be realized by a regular BFS:

1. Duplicate each matched node [math]\displaystyle{ v }[/math] giving [math]\displaystyle{ v_1 }[/math] and [math]\displaystyle{ v_2 }[/math].
2. Replace each edge [math]\displaystyle{ \{v,w\} }[/math] by two arcs, [math]\displaystyle{ (v,w) }[/math] and [math]\displaystyle{ (w,v) }[/math].
3. For each matched node [math]\displaystyle{ v }[/math]:
   1. Let all incoming arcs of [math]\displaystyle{ v }[/math] in [math]\displaystyle{ M }[/math] point to [math]\displaystyle{ v_1 }[/math] and all outgoing arcs in [math]\displaystyle{ E\setminus M }[/math] leave [math]\displaystyle{ v_1 }[/math].
   2. Mirror-symmetrically, let all incoming arcs of [math]\displaystyle{ v }[/math] in [math]\displaystyle{ E\setminus M }[/math] point to [math]\displaystyle{ v_2 }[/math] and all outgoing arcs of [math]\displaystyle{ v }[/math] in [math]\displaystyle{ M }[/math] leave [math]\displaystyle{ v_2 }[/math].