7.4.3. A Simple \(\boldsymbol{O(nm)}\)-Time Algorithm

The maximum-cardinality matching algorithm discussed in this section is similar in spirit to augmenting path maximum-flow algorithms. We start with the trivial matching \(M = \emptyset\) and then improve the matching by repeatedly finding an augmenting path \(P\) and replacing \(M\) with \(M \oplus P\).¹ Once no augmenting path exists, the current matching \(M\) is a maximum-cardinality matching, by Corollary 7.9, so we return this matching \(M\).

By Lemma 7.11, we can decide whether there exists an augmenting path for the current matching \(M\) and, if so, find such a path \(P\) in \(O(n + m)\) time. Since \(|M \oplus P| > |M|\) for every matching \(M\) and every augmenting path \(P\) for \(M\), and since a matching cannot have more than \(\frac{n}{2}\) edges, the algorithm has at most \(\frac{n}{2}\) iterations. Thus, the running time of the algorithm is \(O((n + m)m)\).

This bound can be improved to \(O(nm)\) using the following simple trick: Observe that an isolated vertex cannot be the endpoint of an edge in the computed matching (because it has no incident edges at all). Thus, we can remove these vertices from \(G\) before running the maximum matching algorithm. This takes \(O(n)\) time. After removing isolated vertices, \(G\) has \(n' \le 2m\) vertices, so each iteration of the maximum matching algorithm now takes \(O(n' + m) = O(m)\) time. The cost of all at most \(\frac{n}{2}\) iterations is thus \(O(nm)\). Adding the \(O(n)\) cost of removing isolated vertices, the cost of the whole algorithm is \(O(n + nm) = O(nm)\). This proves the following lemma:

Lemma 7.12: A maximum-cardinality matching in a bipartite graph can be found in \(O(nm)\) time.