6.6.2.2. Maintenance of Non-Negative Residual Costs

To ensure that the algorithm maintains Invariant 6.23, we need to fill in one more step of the algorithm. Without it, Invariant 6.23 does not hold!

I already pointed out the difference between the reduced cost optimality invariant maintained by the successive shortest paths algorithm (Invariant 6.20) and the weaker Invariant 6.23: Invariant 6.23 does not guarantee non-negative reduced costs for the edges of \(G^f\) that are not in \(G^{f,\Delta}\). When transitioning from the \(\Delta\)-phase to the \(\frac{\Delta}{2}\)-phase, note that \(G^{f,\Delta/2}\) may include some edges of \(G^f\) that are not in \(G^{f,\Delta}\): These are all the edges with residual capacities between \(\frac{\Delta}{2}\) and \(\Delta\). Thus, even though Invariant 6.23 holds for \(G^{f,\Delta}\) at the end of the \(\Delta\)-phase, it is not guaranteed to hold for \(G^{f,\Delta/2}\) at the beginning of the \(\frac{\Delta}{2}\)-phase.

We begin by arguing that the invariant does hold at the beginning of the first phase, and we show how we can restore the invariant at the beginning of every subsequent phase. We conclude the discussion in this section by showing that once Invariant 6.23 holds, the updates to \(f\) and \(\pi\) performed during the \(\Delta\)-phase do not invalidate the invariant. Thus, Invariant 6.23 is indeed maintained throughout the \(\Delta\)-phase.

The Beginning of the First Phase

In the analysis of the successive shortest paths algorithm, we observed that setting \(f_e = 0\) for every edge \(e \in G\) and \(\pi_x = 0\) for every vertex \(x \in G\) ensures that \(c^\pi_e \ge 0\) for every edge \(e \in G^f\). Since \(G^{f,\Delta} \subseteq G^f\), this shows that Invariant 6.23 holds at the beginning of the first phase of the capacity scaling algorithm.

Initialization of Any \(\boldsymbol{\Delta}\)-Phase Other Than the First Phase

To ensure that all edges in \(G^{f,\Delta}\) satisfy \(c^\pi_e \ge 0\), that is, that Invariant 6.23 holds at the beginning of the \(\Delta\)-phase, we use the same trick we used in Section 6.3.4 to ensure that all edges in \(G\) have non-negative costs: We saturate all edges with negative cost.

Specifically, we replace \(f\) with the pseudo-flow \(f'\) defined as

\[f'_{x,y} = \begin{cases} 0 & \text{if } (y,x) \in G^{f,\Delta} \text{ and } c^\pi_{y,x} < 0\\ u_{x,y} & \text{if } (x,y) \in G^{f,\Delta} \text{ and } c^\pi_{x,y} < 0\\ f_{x,y} & \text{otherwise} \end{cases}\]

and we leave the potential function \(\pi\) unchanged.

Note that \(f'\) is well defined, that is, that every edge \((x,y) \in G\) satisfies \(f'_{x,y} < \infty\). Indeed, every edge \((x,y) \in G\) satisfies \(f_{x,y} < \infty\). In the first and last cases, we set \(f'_{x,y} = 0\) or \(f'_{x,y} = f_{x,y}\), so \(f'_{x,y}\) is finite in these cases. In the second case, we can have \(f'_{x,y} = \infty\) only if \(u_{x,y} = \infty\). However, if \(u_{x,y} = \infty\), then \(u^f_{x,y} = \infty \ge 2\Delta\), that is, \((x,y) \in G_{f,2\Delta}\) and, by Invariant 6.23, we have \(c^\pi_{x,y} \ge 0\) at the end of the \(2\Delta\)-phase. Thus, the second case can apply only to capacitated edges and \(f'_{x,y} < \infty\) in this case as well.

Since \(f\) is a pseudo-flow at the end of the \(2\Delta\)-phase, \(f'\) is clearly also a pseudo-flow. The next lemma shows that \(f'\) and \(\pi\) satisfy Invariant 6.23, that is, replacing \(f\) with \(f'\) ensures that Invariant 6.23 holds at the beginning of the \(\Delta\)-phase.

Lemma 6.26: \(c^\pi_e \ge 0\) for every edge \(e \in G^{f',\Delta}\).

Proof: Assume for the sake of contradiction that \(G^{f',\Delta}\) contains an edge \((x,y)\) that satisfies \(c^\pi_{x,y} < 0\).

If \((x,y) \in G\), then \(f'_{x,y} < f_{x,y}\) only if \((y,x) \in G^{f,\Delta}\) and \(c^\pi_{y,x} < 0\). Since \(c^\pi_{x,y} = -c^\pi_{y,x}\), this immediately implies that \(c^\pi_{x,y} > 0\), a contradiction. Thus, if \((x,y) \in G\), we have \(f'_{x,y} \ge f_{x,y}\) and, thus, \(u^f_{x,y} = u_{x,y} - f_{x,y} \ge u_{x,y} - f'_{x,y} = u^{f'}_{x,y} \ge \Delta\), that is, \((x,y) \in G^{f,\Delta}\). Since \(c^\pi_{x,y} < 0\), this implies that \(f'_{x,y} = u_{x,y}\), so \(u^{f'}_{x,y} = 0\) and \((x,y) \notin G^{f',\Delta}\), again a contradiction.

If \((y,x) \in G\), then \(f'_{y,x} > f_{y,x}\) only if \((y,x) \in G^{f,\Delta}\) and \(c^\pi_{y,x} < 0\). Once again, this immediately implies that \(c^\pi_{x,y} > 0\), a contradiction. Thus, if \((y,x) \in G\), we have \(f'_{y,x} \le f_{y,x}\) and, thus, \(u^f_{x,y} = f_{y,x} \ge f'_{y,x} = u^{f'}_{x,y} \ge \Delta\), that is, \((x,y) \in G^{f,\Delta}\). Since \(c^\pi_{x,y} < 0\), this implies that \(f'_{y,x} = 0\), so \(u^{f'}_{x,y} = 0\) and \((x,y) \notin G^{f',\Delta}\), again a contradiction. ▨

Updates of \(\boldsymbol{f}\) and \(\boldsymbol{\pi}\) During the \(\boldsymbol{\Delta}\)-Phase

As we have just shown, after the initialization of the \(\Delta\)-phase, Invariant 6.23 holds. The remainder of the \(\Delta\)-phase repeatedly computes the distances of all vertices in \(G^{f,\Delta}\) from some excess vertex \(s\) with excess at least \(\Delta\) and sends flow along a shortest path in \(G^{f,\Delta}\) from \(s\) to some deficit vertex \(t\) with deficit at least \(\Delta\).

This is exactly what the successive shortest paths algorithm does in each iteration, only it uses distances and shortest paths in \(G^f\). By replacing \(G^f\) with \(G^{f,\Delta}\) in the proof of Lemma 6.21, we immediately obtain the following lemma:

Lemma 6.27: If \(c^\pi_{x,y} \ge 0\) for every edge \((x,y) \in G^{f,\Delta}\), then \(c^{\pi'}_{x,y} \ge 0\) for every edge \((x,y) \in G^{f',\Delta}\).

Thus, the \(\Delta\)-phase maintains Invariant 6.23.