7.6.1.4. Abort When There's No Perfect Matching

The implementation of the Hungarian algorithm discussed so far behaves exactly like the \(O\bigl(n^3\bigr)\)-time implementation of the Hungarian algorithm but uses efficient data structures to reduce the running time to \(O\bigl(n^2\lg n + nm\bigr)\). We will discuss that this is indeed the running time of the algorithm in Section 7.6.1.5. In this section, we address how we detect that \(G\) has no perfect matching whenever this is the case.

As already stated in Section 7.6.1.3, whenever the vertex \(w \in \bar Y\) with minimum slack \(\delta_w\) satisfies \(\delta_w = \infty\), we abort the algorithm and report that \(G\) has no perfect matching. Next we prove that this is correct.

Lemma 7.26: If \(M\) is not a perfect matching, all vertices in \(Y\) are matched, \(\bar Y \ne \emptyset\), and all vertices in \(\bar Y\) have infinite slack, then there is no perfect matching.

Proof: Since we assume that the current matching \(M\) is not a perfect matching, to prove that there is no perfect matching, it suffices to show that \(M\) is a maximum-cardinality matching.

So assume for the sake of contradiction that \(M\) is not a maximum matching. Then there exists an augmenting path \(P\) for \(M\). Since \(G\) is bipartite, \(P\) has an unmatched endpoint \(u \in U\) and an unmatched endpoint \(w \in W\). Since we start the phase by adding all unmatched vertices in \(U\) to \(X\), we have \(u \in X\). Since we assume that all vertices in \(Y\) are matched (otherwise, the phase would end because we have found a tight augmenting path), we have \(w \in \bar Y\). Thus, \(P\) starts in \(X \cup Y\) and ends in \(\bar X \cup \bar Y\). Let \(z\) be the vertex in \(P\) closest to \(u\) that belongs to \(\bar X \cup \bar Y\).

If \(z \in \bar Y\), then by the choice of \(z\), its predecessor \(u'\) in \(P\) belongs to \(X\). Thus, we have a vertex \(z \in \bar Y\) that has a neighbour in \(X\). Since all edge costs are finite, this implies that \(\delta_z < \infty\), a contradiction.

If \(z \in \bar X\), then by the choice of \(z\), its predecessor \(w'\) in \(P\) belongs to \(Y\). Moreover, the subpath of \(P\) from \(u\) to \(z\) is even and the edge \((w', z)\) is in \(M\). Since we move the mate of every vertex \(w' \in Y\) from \(\bar X\) to \(X\) when moving \(w'\) from \(\bar Y\) to \(Y\), we thus have \(z \in X\), again a contradiction.

Thus, there exists no augmenting path for \(M\) and \(M\) is a maximum-cardinality matching. ▨