6.6.1. Overview of the Algorithm

As already mentioned, the capacity scaling algorithm is variant of the successive shortest paths algorithms. It maintains a pseudo-flow \(f\) and a potential function \(\pi\). When the algorithm terminates, \(f\) is a flow, and \(f\) and \(\pi\) satisfy the reduced cost optimality criterion. Thus, \(f\) is a minimum-cost flow at this point.

Initialization

The initialization of the algorithm is the same as for the successive shortest paths algorithm: We set \(f_e = 0\) for every edge \(e \in G\), and we set \(\pi_x = 0\) for every vertex \(x \in G\). As discussed in Section 6.5, this ensures that \(f\) and \(\pi\) satisfy the reduced cost optimality criterion, but \(f\) is not a feasibly flow unless we have no supply vertices and no demand vertices.

Finding a Feasible Flow

Also as in the successive shortest paths algorithm, we now repeatedly update \(f\) and \(\pi\) until \(f\) is a feasible flow, while ensuring that \(f\) and \(\pi\) continue to satisfy reduced cost optimality. The manner in which we perform these updates is where the capacity scaling algorithm differs from the successive shortest paths algorithm.

The updates of \(f\) and \(\pi\) are organized into phases. Each phase has an associated parameter \(\Delta\). In this phase, we only perform flow augmentations that send at least \(\Delta\) units of flow from an excess vertex to a deficit vertex. Given this dependence of the phase on \(\Delta\), we call this phase the \(\Delta\)-phase.

In the first phase, we set \(\Delta = 2^{\lfloor \lg U\rfloor}\). In each subsequent phase, we halve \(\Delta\) until \(\Delta = 1\) in the final phase. Thus, there are \(\lfloor \lg U \rfloor\) phases.

The \(\Delta\)-Phase

The \(\Delta\)-phase of the algorithm performs only flow augmentations that send at least \(\Delta\) units of flow from an excess vertex to a deficit vertex. To find paths along which we can send at least \(\Delta\) units of flow, the \(\Delta\)-phase works with a subgraph \(G^{f,\Delta} = \bigl(V, E^{f,\Delta}\bigr)\) of the residual network \(G^f = \bigl(V, E^f\bigr)\), where

\[E^{f,\Delta} = \bigl\{e \in E^f \mid u^f_e \ge \Delta\bigr\}.\]

We call \(G^{f,\Delta}\), the \(\Delta\)-residual network.

As long as there exists an excess vertex with excess at least \(\Delta\) and a deficit vertex with deficit at least \(\Delta\), we pick an arbitrary excess vertex \(s\) with excess at least \(\Delta\) and an arbitrary deficit vertex \(t\) with deficit at least \(\Delta\), we find a shortest path \(P\) from \(s\) to \(t\) in \(G^{f,\Delta}\), and then we send \(\delta\) units of flow from \(s\) to \(t\), where

\[\delta = \min\bigl(\bigl\{e_s, -e_t\bigr\} \cup \bigl\{c^f_e \mid e \in P\bigr\}\bigr).\]

Since \(P\) is a path in \(G^{f,\Delta}\), we have \(\delta \ge \Delta\), that is, we do indeed send at least \(\Delta\) units of flow from \(s\) to \(t\).

Sending \(\delta\) units of flow along \(P\) means that we replace \(f\) with the flow \(f'\) defined as

\[f'_{x,y} = \begin{cases} f_{x,y} + \delta & \text{if } (x, y) \in P\\ f_{x,y} - \delta & \text{if } (y, x) \in P\\ f_{x,y} & \text{otherwise.} \end{cases}\]

By Lemma 5.1, \(f'\) is once again a pseudo-flow in \(G\).

We also replace the potential function \(\pi\) with a new potential function \(pi'\) defined as

\[\pi'_x = \pi_x - d_x,\]

where \(d_x\) is the distance from \(s\) to \(x\) in \(G^{f,\Delta}\), which we compute as part of finding a shortest path from \(s\) to \(t\) in \(G^{f,\Delta}\).

Once again, this is exactly the same strategy used by the successive shortest paths algorithm. An important difference, one with implications we need to address, is that \(P\) is a shortest path in \(G^{f,\Delta}\), not in \(G^f\). There may exist a shorter path from \(s\) to \(t\) in \(G^f\), but it includes edges whose residual capacity is less than \(\Delta\). Similarly, the distance \(d_x\) subtracted from \(\pi_x\) to obtain \(\pi'_x\) for every vertex is the distance from \(s\) to \(x\) in \(G^{f,\Delta}\), not in \(G^f\).

Also as in the successive shortest paths algorithm, a path \(P\) from \(s\) to \(t\) in \(G^{f,\Delta}\) always exists because \(G\) contains an uncapacitated path from \(s\) to \(t\) and this path is then also part of \(G^{f,\Delta}\).

The \(\Delta\)-phase continues picking pairs of vertices \((s, t)\) such that \(s\) is an excess vertex with excess at least \(\Delta\) and \(t\) is a deficit vertex with deficit at least \(\Delta\) and sending flow from \(s\) to \(t\) along a shortest path in \(G^{f,\Delta}\) for each such pair, until there are either no more excess vertices with excess at least \(\Delta\) or no more deficit vertices with deficit at least \(\Delta\), possibly both.

Once we run out of excess vertices with excess at least \(\Delta\) or out of deficit vertices with deficit at least \(\Delta\), the \(\Delta\)-phase ends. If \(\Delta = 1\), then this is the last phase of the algorithm, and the algorithm returns the pseudo-flow \(f\) obtained at the end of the \(\Delta\)-phase. If \(\Delta > 1\), then we set \(\Delta = \frac{\Delta}{2}\) and start the next phase.