7.5.2.2. Correctness of Each Iteration

We already argued that the matching \(M \oplus P_w\) produced by an iteration that finds an augmenting path is \(F^\pi\) is once again composed of only tight edges. Thus, each such iteration maintains complementary slackness.

Next we prove that every edge in \(M\) remains tight with respect to the potential function

\[\pi_v' = \begin{cases} \pi_v + \delta & \text{if } v \in X\\ \pi_v - \delta & \text{if } v \in Y\\ \pi_v & \text{otherwise}, \end{cases}\]

where \(X\) and \(Y\) are the subsets of vertices in \(U\) and \(W\), respectively, that belong to \(F^\pi\), \(\bar X = U \setminus X\), and \(\bar Y = W \setminus Y\), and

\[\delta = \min_{u \in X, w \in \bar Y}(c_{u,w} - \pi_u - \pi_w).\]

We also prove that \(|Y'| > |Y|\), where \(X'\) and \(Y'\) are the subsets of vertices in \(U\) and \(W\), respectively, that belong to \(F^{\pi'}\), \(\bar X' = U \setminus X'\), and \(\bar Y' = W \setminus Y'\). Thus, it takes at most \(n\) iterations to include all vertices in \(W\) in \(F^\pi\), at which point we are guaranteed to find an augmenting path to grow \(M\), unless \(M\) is already a perfect matching.

Lemma 7.18: If the potential function \(\pi\) is feasible and every edge in \(M\) is tight with respect to \(\pi\), then \(\pi'\) is feasible and every edge in \(M\) is tight with respect to \(\pi'\).

Proof: First observe that \(\delta \ge 0\) because \(\pi\) is a feasible potential function, that is, every edge \((u,w) \in E\) satisfies \(c_{u,w} - \pi_u - \pi_w \ge 0\).

Since we have \(\pi_w \le 0\) and \(\pi'_w = \pi_w\) or \(\pi'_w = \pi_w - \delta\) for every vertex \(w \in W\), this immediately implies that \(\pi'_w \le 0\) for every vertex \(w \in W\).

Next observe that every edge \((u,w) \in E\) satisfies

\[\bigl(\pi'_u + \pi'_w\bigr) - (\pi_u + \pi_w) = \begin{cases} \hphantom{-}\delta & \text{if } u \in X \text{ and } w \in \bar Y\\ -\delta & \text{if } u \in \bar X \text{ and } w \in Y\\ \hphantom{-}0 & \text{otherwise}. \end{cases}\tag{7.9}\]

Thus, unless \(u \in X\) and \(w \in \bar Y\), we have \(\pi'_u + \pi'_w \le \pi_u + \pi_w \le c_{u,w}\). If \(u \in X\) and \(w \in \bar Y\), then, by the choice of \(\delta\), we have \(\pi'_u + \pi'_w = \pi_u + \pi_w + \delta \le \pi_u + \pi_w + (c_{u,w} - \pi_u - \pi_w) = c_{u,w}\).

Since \(\pi_w' \le 0\) for all \(w \in W\) and \(\pi_u' + \pi_w' \le c_{u,w}\) for all \((u,w) \in E\), \(\pi'\) is a feasible potential function.

By the next lemma, each edge \((u,w) \in M\) satisfies \(u \in X\) and \(w \in Y\) or \(u \in \bar X\) and \(w \in \bar Y\). Thus, by (7.9), \(\pi_u' + \pi_w' = \pi_u + \pi_w\). Since every edge in \(M\) is tight with respect to \(\pi\), it is therefore also tight with respect to \(\pi\). ▨

Lemma 7.19: Every edge \((u,w) \in M\) satisfies \(u \in X\) if and only if \(w \in Y\).

Proof: Assume that \(u \in X\). Then there exists a tight alternating path \(P\) from some unmatched vertex \(u' \in U\) to \(u\). Since \(u \in U\), this path is even, that is, its last edge is in \(M\). Since \((u,w)\) is the only edge in \(M\) incident to \(u\) (\(M\) is a matching), \(w\) must be \(u\)'s predecessor in \(P\) and the subpath of \(P\) from \(u'\) to \(w\) is a tight alternating path from \(u'\) to \(w\). Therefore, \(w \in Y\).

Now assume that \(w \in Y\). Then there exists a tight alternating path \(P\) from some unmatched vertex \(u' \in U\) to \(w\). Since \(w \in W\), this path is odd, that is, its last edge is not in \(M\). Since \((u,w) \in M\), the edge \((u,w)\) is tight. Thus, appending this edge to \(P\) gives a tight alternating path from \(u'\) to \(u\), and \(u \in X\). ▨

Lemma 7.20: The alternating forest \(F^{\pi'}\) with respect to \(\pi'\) contains more vertices from \(W\) than the alternating forest \(F^{\pi}\) with respect to \(\pi\).

Proof: Let \(X\), \(Y\), \(\bar X\), \(\bar Y\), \(X'\), \(Y'\), \(\bar X'\), and \(\bar Y'\) be defined as above. The lemma claims that \(|Y'| > |Y|\). To prove this, it suffices to prove that \(X \subseteq X'\) and \(Y \subset Y'\).

We start by proving that \(X \subseteq X'\) and \(Y \subseteq Y'\). Then we prove that \(Y'\) contains at least one vertex that is not in \(Y\). Thus, \(Y \subset Y'\).

The vertex set of \(F^\pi\) is \(X \cup Y\). Assume that there exists a vertex \(z \in X \cup Y\) that is not in \(F^{\pi'}\). Then choose this vertex so that the length of the path \(P_z\) from \(z\) to \(r_z\) in \(F^{\pi}\) is minimized. Let \(v\) be \(z\)'s predecessor in \(P_z\). By the choice of \(z\), \(v \in F^{\pi'}\). Thus, there exists a tight alternating path \(P'_v\) with respect to \(\pi'\) from an unmatched vertex \(u \in U\) to \(v\). Note that the edge \((v,z)\) is tight with respect to \(\pi\) because it belongs to \(P_z\). Since \(v, z \in F^\pi\), we have either \(v \in X\) and \(z \in Y\) or \(v \in Y\) and \(z \in X\). In both cases, \(\pi'_v + \pi'_z = \pi_v + \pi_z = c_{v,z}\), that is, the edge \((v,z)\) is tight also with respect to \(\pi'\).

Now, if \(z \in U\), then the path \(P_z\) is even, so the edge \((v,z)\) is in \(M\), \(v \in W\), and the path \(P'_v\) is odd. If \(z \in W\), then the path \(P_z\) is odd, so the edge \((v,z)\) is not in \(M\), \(v \in U\), and the path \(P'_v\) is even. In both cases, appending the edge \((v,z)\) to the path \(P'_v\) produces a tight alternating path from \(u\) to \(z\) with respect to \(\pi'\), that is, \(z \in X' \cup Y'\) (unless \(z \in P'_v\), in which case \(z\) also belongs to \(X' \cup Y'\)), a contradiction. This proves that \(X \cup Y \subseteq X' \cup Y'\), that is, \(X \subseteq X'\) and \(Y \subseteq Y'\).

Next consider any edge \((u,w)\) such that \(u \in X\), \(w \in \bar Y\), and \(c_{u,w} - \pi_u - \pi_w = \delta\). By the definition of \(\delta\), such an edge exists. This edge satisfies \(\pi'_u + \pi'_w = \pi_u + \pi_w + \delta = \pi_u + \pi_w + (c_{u,w} - \pi_u - \pi_w) = c_{u,w}\), that is, this edge is tight with respect to \(\pi'\). Since \(u \in X\) and \(X \subseteq X'\), there exists a tight alternating path \(P'_u\) with respect to \(\pi'\) from some unmatched vertex \(u' \in U\) to \(u\). Since \(u \in U\), this path is even and therefore ends in an edge in \(M\). By Lemma 7.19, \((u,w) \notin M\). Thus, the path obtained by appending the edge \((u,w)\) to \(P'_u\) is a tight alternating path from \(u'\) to \(w\) with respect to \(\pi'\), that is, \(w \in Y'\). Since \(w \in \bar Y\), this shows that \(Y \subset Y'\). ▨