7.5.2.3. Summary of the Algorithm

Let us summarize how the Hungarian algorithm works.

We start with an empty matching \(M = \emptyset\) and a feasible potential function \(\pi\). This choice guarantees that complementary slackness holds initially.

Then each iteration either finds a tight augmenting path \(P\) composed of tight edges, or it replaces \(\pi\) with a new potential function \(\pi'\) such that \(F^{\pi'}\) includes more vertices in \(W\) than \(F^\pi\) does and all edges in \(M\) remain tight with respect to \(\pi'\). We can do the latter at most \(n\) times before we are guaranteed to find a tight augmenting path in \(F^\pi\). Thus, each phase has at most \(n + 1\) iterations. Since the algorithm needs \(n\) phases to arrive at a perfect matching, it terminates after \(O\bigl(n^2\bigr)\) iterations. Since we maintain complementary slackness at all times, the final matching is in fact a minimum-weight perfect matching.

To bound the running time of the algorithm by \(O\bigl(n^4\bigr)\), it suffices to prove that each iteration takes \(O\bigl(n^2\bigr)\) time.

Observe that it takes \(O(n + m) = O\bigl(n^2\bigr)\) time to identify the current tight subgraph \(G^\pi\) of \(G\) and find an alternating forest \(F^\pi\) of \(G^\pi\). If \(F^\pi\) contains an unmatched vertex \(w \in W\), it takes \(O(n)\) extra time to trace the path \(P_w\) in \(F^\pi\) from \(w\) to \(r_w\) and augment \(M\) with \(P_w\). Thus, the last iteration of each phase takes \(O\bigl(n^2\bigr)\) time.

If \(F^\pi\) contains no unmatched vertex in \(W\), then it takes \(O\bigl(n^2\bigr)\) time to inspect all edges between vertices in \(X\) and vertices in \(\bar Y\) to determine \(\delta\) and \(O(n)\) additional time to add \(\delta\) to the potential of every vertex in \(X\) and subtract \(\delta\) from the potential of every vertex in \(Y\). Thus, any iteration that is not the last iteration in its phase also takes \(O\bigl(n^2\bigr)\) time.

Since the algorithm runs for at most \(n^2 + n\) iterations and each iteration takes \(O\bigl(n^2\bigr)\) time, the algorithm runs in \(O\bigl(n^4\bigr)\) time. Thus, we obtain the following result:

Theorem 7.21: The Hungarian Algorithm takes \(O\bigl(n^4\bigr)\) time to find a minimum-weight perfect matching in a complete bipartite graph \(G = (U, W, E)\) with \(|U| = |W| = n\).