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: In a loop over all exposed nodes [math]\displaystyle{ v }[/math], a graph traversal algorithm is started at [math]\displaystyle{ v }[/math]. An algorithm must be chosen that generates an arborescence rooted at the start node [math]\displaystyle{ v }[/math], for example, a DFS or a BFS. This terminates once an augmenting path has been found. To find an augmenting path, 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.

Remark on the implementation: This modified graph traversal in an undirected graph could be implemented as a regular graph traversal in a directed graph:

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].

Proof: Basically, we have to show that there is no more augmenting path if this repeated graph search 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] from [math]\displaystyle{ u }[/math] to some other exposed node [math]\displaystyle{ v }[/math]. Then [math]\displaystyle{ v }[/math] is not seen by this graph search. Let [math]\displaystyle{ x }[/math] be the last node on [math]\displaystyle{ p }[/math] seen by this graph search, let [math]\displaystyle{ e }[/math] denote the edge over which [math]\displaystyle{ x }[/math] was seen, and let [math]\displaystyle{ e' }[/math] be the next edge on [math]\displaystyle{ p }[/math] (as seen in the direction from [math]\displaystyle{ u }[/math] to [math]\displaystyle{ v }[/math]). Since [math]\displaystyle{ e }[/math] was considered by the graph search and [math]\displaystyle{ e' }[/math] was not, we may conclude [math]\displaystyle{ e,e'\not\in M }[/math]. Let [math]\displaystyle{ p' }[/math] be the subpath of [math]\displaystyle{ p }[/math] from [math]\displaystyle{ u }[/math] to [math]\displaystyle{ x }[/math] and [math]\displaystyle{ p'' }[/math] the path from [math]\displaystyle{ u }[/math] to [math]\displaystyle{ x }[/math] in the arborescence. As [math]\displaystyle{ e'\not\in M }[/math], the last edge of [math]\displaystyle{ p' }[/math] is in [math]\displaystyle{ M }[/math], so [math]\displaystyle{ p' }[/math] has even length. Since [math]\displaystyle{ e\not\in M }[/math], [math]\displaystyle{ p'' }[/math] has odd length. In summary, the concatenation [math]\displaystyle{ p'+p'' }[/math] is a (usually non-simple) cycle of odd length. In particular, [math]\displaystyle{ G }[/math] is not bipartite.

Remark on the proof: Let [math]\displaystyle{ y }[/math] denote the node up to which [math]\displaystyle{ p' }[/math] and [math]\displaystyle{ p'' }[/math] are identical, and let [math]\displaystyle{ z }[/math] denote the next node of [math]\displaystyle{ p' }[/math] that also belongs to [math]\displaystyle{ p'' }[/math]. In case [math]\displaystyle{ y\neq u }[/math], the subpaths of [math]\displaystyle{ p' }[/math] and [math]\displaystyle{ p'' }[/math] from [math]\displaystyle{ x }[/math] to [math]\displaystyle{ y }[/math] form a blossom, and the graph search entered this blossom via its stem.

Correctness

Berge's theorem immediately implies that the resulting matching is cardinality-maximal.

Complexity

Statement: The asymptotic complexity is in [math]\displaystyle{ \mathcal{O}(n\!\cdot\!m) }[/math], where [math]\displaystyle{ n=|V| }[/math] and [math]\displaystyle{ m=|E| }[/math].

Proof: Since a matching cannot have more than [math]\displaystyle{ |V|/2 }[/math] edges, the number of iterations is linear in the number of nodes. The complexity of an iteration is dominated by the graph search.

Connection to max-flow

This algorithm may be interpreted as an application of Ford-Fulkerson:

1. Let [math]\displaystyle{ \{V_1,V_2\} }[/math] denote a bipartition of [math]\displaystyle{ V }[/math] such that each edge is incident to one node of [math]\displaystyle{ V_1 }[/math] and one node of [math]\displaystyle{ V_2 }[/math].
2. Replace each undirected edge [math]\displaystyle{ \{v,w\} }[/math] by the directed arc [math]\displaystyle{ (v,w) }[/math] with infinite capacity, where [math]\displaystyle{ v\in V_1 }[/math] and [math]\displaystyle{ w\in V_2 }[/math] (so, all arcs go from [math]\displaystyle{ V_1 }[/math] to [math]\displaystyle{ V_2 }[/math]).
3. Insert a new super-source [math]\displaystyle{ s }[/math] and a new super-target [math]\displaystyle{ t }[/math] in [math]\displaystyle{ V }[/math].
4. For each node [math]\displaystyle{ v\in V_1 }[/math], insert an arc [math]\displaystyle{ (s,v) }[/math] with capacity one.
5. Mirror-symmetrically, for each node [math]\displaystyle{ w\in V_2 }[/math], insert an arc [math]\displaystyle{ (w,t) }[/math] with capacity one.

There is an obvious one-to-one correspondence between integral flows in that network and matchings in the original graph: An edge belongs to the matching if, and only if, the corresponding arc has positive flow value. The maximum flows correspond to the cardinality-maximal matchings. There is also a one-to-one correspondence between augmenting paths in the original graph and flow-augmenting paths in the induced flow network. Augmenting the matching along an augmenting path is tantamount to augmenting the flow along the corresponding flow-augmenting path. Finally, the max-flow min-cut theorem reduces to the famous min-max theorem for bipartite matchings:

Definition:

1. A node cover in an undirected graph is a set of nodes such that each edge is incident to at least one node in this set.
2. A node in a node cover is said to cover the edges incident to this node.

Min-max theorem: In a bipartite graph, the maximum cardinality of a matching equals the minimum cardinality of a node cover.

Reduction to the max-flow min-cut theorem: Let [math]\displaystyle{ M }[/math] be a cardinality-maximal matching. No node can cover more than one edge of [math]\displaystyle{ M }[/math]. Therefore, no node set of less than [math]\displaystyle{ |M| }[/math] nodes can be a node cover. Thus, it suffices to construct a node cover of cardinality [math]\displaystyle{ M }[/math].

Since all arcs leaving [math]\displaystyle{ s }[/math] have finite capacities, the minimum [math]\displaystyle{ (s,t) }[/math]-cut has finite capacity, too. So, let [math]\displaystyle{ (S,T) }[/math] be some [math]\displaystyle{ (s,t) }[/math]-cut with finite capacity. In particular, [math]\displaystyle{ (S,T) }[/math] is only crossed by arcs from [math]\displaystyle{ s }[/math] to [math]\displaystyle{ T }[/math] and by arcs from [math]\displaystyle{ S }[/math] to [math]\displaystyle{ t }[/math]. Now, let [math]\displaystyle{ S':=S\cap V_2 }[/math] and [math]\displaystyle{ T':=T\cap V_1 }[/math]. The node sets [math]\displaystyle{ S' }[/math] and [math]\displaystyle{ T' }[/math] are disjoint. The nodes in [math]\displaystyle{ S' }[/math] are in one-to-one correspondence to the arcs from [math]\displaystyle{ s }[/math] to [math]\displaystyle{ T }[/math], and the nodes in [math]\displaystyle{ T' }[/math] are in one-to-one correspondence to the arcs from [math]\displaystyle{ S }[/math] into [math]\displaystyle{ t }[/math]. In summary, [math]\displaystyle{ |S'\cup T'| }[/math] is the capacity of [math]\displaystyle{ (S,T) }[/math]. It suffices to show that [math]\displaystyle{ S'\cup T }[/math] is a node cover for the original graph.

For a contradiction suppose some edge [math]\displaystyle{ \{v,w\} }[/math] is not covered, where [math]\displaystyle{ v\in V_1 }[/math] and [math]\displaystyle{ w\in V_2 }[/math], say. So, it is [math]\displaystyle{ v\in S }[/math] and [math]\displaystyle{ w\in T }[/math], However, then [math]\displaystyle{ (v,w) }[/math] would go from [math]\displaystyle{ S }[/math] to [math]\displaystyle{ T }[/math], which contradicts the choice of [math]\displaystyle{ (S,T) }[/math] to have finite capacity.

Comment: Tutte's theorem extends the min-max theorem to non-bipartite graphs.