7.4. Bipartite Maximum-Cardinality Matching

We have shown in Section 7.3 that a maximum-cardinality, maximum-weight or minimum-weight perfect matching in a bipartite graph can be found in polynomial time by transforming the problem into a maximum flow or minimum-cost flow problem in some network \(\vec{G}\). Next we show that all these types of matchings can be found more efficiently, without the detour via network flows. We start by discussing the maximum-cardinality matching problem, still in bipartite graphs.

• Section 7.4.1 introduces the key concept we use to find matchings of various kinds: augmenting paths. All matching algorithms start with some matching, often the trivial matching \(M = \emptyset\), and then look for augmenting paths to make the matching bigger. We prove that a matching is a maximum-cardinality matching if and only if there does not exist an augmenting path with respect to this matching.

  Note the similarity to augmenting path maximum-flow algorithms. Those algorithms start with the trivial flow \(f = 0\) and then look for augmenting paths along which to send more flow from \(s\) to \(t\). Just as we claim here that a matching is a maximum-cardinality matching if and only if it has no augmenting path, we proved that a flow is a maximum \(st\)-flow if and only if there exists no augmenting path for this flow. The only difference is that we now talk about a different kind of augmenting path, because we want to construct matchings, not flows.

• Section 7.4.2 introduces alternating forests as a tool for finding augmenting paths. We prove that such a forest can be found in \(O(n + m)\) time using an adaptation of breadth-first search (BFS), called alternating BFS and that such a forest can be used to decide whether a bipartite graph has an augmenting path for a given matching and, if so, find one. Note that this latter part relies crucially on the graph being bipartite: If the graph is not bipartite, then deciding whether there exists an augmenting path and finding such a path are much harder, as we will see in Section 7.7.

• The algorithms for finding an alternating forest and for using it to find an augmenting path in a bipartite graph, discussed in Section 7.4.2, immediately lead to a simple \(O(nm)\)-time algorithm to find a maximum-cardinality matching in a bipartite graph. We discuss this algorithm in Section 7.4.3.

• Most algorithms we discuss in this chapter find one augmenting path at a time. In Section 7.4.4, we discuss the Hopcroft-Karp algorithm, which applies a strategy reminiscent of Dinitz's maximum flow algorithm to find many augmenting paths simultaneously—the parallel to maximum flow algorithms continues. This allows the Hopcroft-Karp algorithm to find a maximum-cardinality matching in a bipartite graph in \(O\bigl(n + m\sqrt{n}\bigr)\) time.