7.7.1. Edmonds's Algorithm

Let us assume for now that the graph \(G\) for which we want to compute a maximum-cardinality matching is connected. As already said, Edmonds's algorithm uses the same strategy as any other maximum-cardinality matching algorithm: It starts with either the empty matching \(M = \emptyset\) or with a maximal matching \(M\), which can be found in \(O(n + m) = O(m)\) time. Then it repeatedly grows the matching \(M\) by looking for an augmenting path \(P\) and replacing \(M\) with \(M \oplus P\). Once it fails to find an augmenting path \(P\), \(M\) is a maximum-cardinality matching, by Corollary 7.9. We will show that it takes \(O(nm)\) time to find an augmenting path \(P\) in an arbitrary connected graph, or decide that no such path exists. Since we must obtain a maximum-cardinality matching after at most \(\frac{n}{2}\) iterations, we call this algorithm to find an augmenting path at most \(\frac{n}{2}\) times. Thus, we can find a maximum-cardinality matching in a connected graph in \(O\bigl(n^2m\bigr)\) time.

If the input graph is not connected, then we can compute the connected components of the graph in \(O(n + m)\) time and then find maximum-cardinality matchings for all components. The result is clearly a maximum-cardinality matching of the whole graph. If the components are \(G_1, \ldots, G_k\) and \(G_i\) has \(n_i \le n\) vertices and \(m_i\) edges, then \(\sum_{i=1}^k m_i = m\) and the running time of the whole algorithm is

\[\begin{multline} O(n + m) + \sum_{i=1}^k O\bigl(n_i^2m_i\bigr) \le O(n + m) + \sum_{i=1}^k O\bigl(n^2m_i\bigr)\\ = O(n + m) + O\bigl(n^2m\bigr) = O\bigl(n^2m\bigr). \end{multline}\]

Thus, we obtain the following result:

Theorem 7.30: A maximum-cardinality matching in an arbitrary graph \(G\) can be found in \(O\bigl(n^2m\bigr)\) time.

It remains to discuss how to find an augmenting path in a connected graph in \(O(nm)\) time.