6.8.5. Correctness Proof

To establish the correctness of the repeated capacity scaling algorithm, we need to prove that there exists a feasible flow in the compressed graph \(G''\) and that if \(\pi''\) is an optimal potential function for \(G''\), then the potential function \(\pi'\) defined as

\[\pi'_v = \begin{cases} \pi''_z & \text{if } v \in \{x, y\}\\ \pi''_v & \text{if } v \notin \{x, y\} \end{cases}\]

is an optimal potential function for \(G'\).

Lemma 6.50: There exists a feasible flow in \(G''\).

Proof: Since all edges are uncapacitated, we only need to prove that the total supply balance of all nodes in \(0\). Recall the definition of the supply balance function \(b''\) of \(G\): We have

\[b''_v = \begin{cases} b_x + b_y & \text{if } v = z\\ b_v & \text{if } v \ne z. \end{cases}\]

Thus,

\[\sum_{v \in G''} b''_v = \sum_{v \in G} b_v = 0.\ \text{▨}\]

Lemma 6.51: The potential function \(\pi'\) is an optimal potential function for \(G'\).

Proof: Consider the dual of the minimum-cost flow LP for \(G'\):

\[\begin{gathered} \text{Maximize } \sum_{v \in V} b_v\pi'_v\\ \text{s.t.}\ \pi'_v - \pi'_w \le c'_{v,w} \quad \forall (v, w) \in G'. \end{gathered}\tag{6.13}\]

The part of the LP (6.3) that refers to capacitated edges is absent because there are no capacitated edges in \(G'\). By Lemma 6.49, any optimal solution to this LP satisfies \(\pi'_x = \pi'_y\). Thus, we can replace \(\pi'_x\) and \(\pi'_y\) with a single variable \(\pi''_z\) and rename all other variables \(\pi'_v\) with \(v \notin \{x, y\}\) in the LP to \(\pi''_v\). Since \(b''_z = b_x + b_y\), this gives the LP

\[\begin{gathered} \text{Maximize } \sum_{v \in V \setminus \{x, y\} \cup \{z\}} b''_v\pi''_v\\ \text{s.t.}\ \pi''_{\phi(v)} - \pi''_{\phi(w)} \le c'_{v, w} \quad \forall (v, w) \in G' \setminus \{(x,y)\}, \end{gathered}\tag{6.14}\]

where

\[\phi_v = \begin{cases} z & \text{if } v \in \{x, y\}\\ v & \text{if } v \notin \{x, y\}. \end{cases}\]

Since any optimal solution to (6.13) satisfies \(\pi'_x = \pi'_y\), (6.13) and (6.14) have the same set of optimal solutions. However, (6.14) is exactly the dual of the minimum-cost flow LP for \(G''\). Thus, any potential function \(\pi'\) defined as \(\pi'_v = \pi''_{\phi(v)}\) for an optimal potential function for \(G''\) is an optimal potential function for \(G'\). ▨