7.6.1.5. Summary

The implementation of the Hungarian Algorithm discussed in this section moves the same sequence of vertices from \(\bar Y\) to \(Y\) and computes the same vertex potentials and augmenting path in each phase as the \(O\bigl(n^3\bigr)\)-time implementation from Section 7.5.3. Thus, the algorithm computes a minimum-weight perfect matching.

By Lemmas 7.24 and 7.25, the initialization and the final iteration of each phase take \(O(n + m)\) time in total. Any iteration that updates \(\pi\) takes constant time. Any other iteration takes \(O(\lg n + \deg(u))\) time, where \(w\) is the vertex moved from \(\bar Y\) to \(Y\) and \(u\) is \(w\)'s mate, which is moved from \(\bar X\) to \(X\). Since each phase has at most \(2n\) iterations and every vertex in \(U\) is moved from \(\bar X\) to \(X\) at most once per phase, the total cost of the initialization and all iterations in a phase is thus \(O(n \lg n + m)\). Summing this over all \(n\) phases of the algorithm, this gives a running time of \(O\bigl(n^2 \lg n + nm\bigr)\) for the whole algorithm. Thus, we have the following result:

Theorem 7.27: A minimum-weight perfect matching in a bipartite graph \(G\) can be computed in \(O\bigl(n^2 \lg n + nm\bigr)\) time if \(G\) has a perfect matching. If \(G\) has no perfect matching, the algorithm detects this and aborts.