6.6.3. Running Time Analysis

As already observed, the capacity scaling algorithm runs for \(\lfloor\lg U\rfloor\) phases. The initialization of each phase is easily seen to take \(O(n + m)\) time: The first phase simply sets every vertex's potential to \(\pi_x = 0\) and every edge's flow to \(f_e = 0\). In any subsequent phase, the initialization does not alter node potentials and updates the flow of every edge based on its current flow and on the potentials of its endpoints. Thus, the initialization of all phases takes \(O((n + m)\lg U)\) time in total.

As in the successive shortest paths algorithm, the cost of each individual flow augmentation is dominated by the cost of computing the distance labels and finding the shortest path along which to move flow from an excess node to a deficit node. Since we use Dijkstra's algorithm to do this, this takes \(O(n \lg n + m)\) time. Next we prove that each phase performs \(O(n + m)\) flow augmentations. Thus, we perform \(O((n + m)\lg U)\) flow augmentations in total, at a total cost of \(O\bigl(\bigl(n^2\lg n + nm\bigr)\lg U\bigr)\). The running time of the algorithm is thus \(O\bigl(\bigl(n^2\lg n + nm\bigr)\lg U\bigr)\).

Lemma 6.28: Each phase of the capacity scaling algorithm performs less than \(n + 2m\) flow augmentations.

Proof: By Invariant 6.24, we have only vertices with excess less than \(2\Delta\) or only vertices with excess greater than \(-2\Delta\) at the beginning of the \(\Delta\)-phase. Since the total excess of all excess vertices equals the total deficit of all deficit vertices, this implies that

\[e_G = \sum_{x \in G} |e_x| = \sum_{\substack{x \in G\\e_x > 0}}e_x - \sum_{\substack{x \in G\\e_x < 0}}e_x < 2\Delta n.\]

The initialization of the \(\Delta\)-phase may update \(f\) to ensure that all edges in \(G^{f,\Delta}\) have non-negative reduced costs and may therefore alter the excesses of the endpoints of the affected edges. So let \(f'\) be the flow with which the initialization of the \(\Delta\)-phase replaces \(f\), and consider any edge \((x,y) \in G\). If \(f'_{x,y} \ne f_{x,y}\), then either \((x,y) \in G^{f,\Delta}\) and \(c^\pi_{x,y} < 0\) or \((y,x) \in G^{f,\Delta}\) and \(c^\pi_{y,x} < 0\).

In the former case, \((x,y) \notin G^{f,2\Delta}\) because \(c^\pi_{w,z} \ge 0\) for every edge \((w,z) \in G^{f,2\Delta}\) at the beginning of the \(\Delta\)-phase, by Invariant 6.23. Thus, \(u_{x,y} - f_{x,y} = u^f_{x,y} < 2\Delta\) and setting \(f'_{x,y} = u_{x,y}\) ensures that \(f'_{x,y} - f_{x,y} < 2\Delta\). Replacing \(f_{x,y}\) with \(f'_{x,y}\) thus changes each of \(e_x\) and \(e_y\) by less than \(2\Delta\) and, thus, \(e_G\) by less than \(4\Delta\).

In the latter case, \((y,x) \notin G^{f,2\Delta}\), again because \(c^\pi_{w,z} \ge 0\) for every edge \((w,z) \in G^{f,2\Delta}\) at the beginning of the \(\Delta\)-phase. Thus, \(f_{x,y} = u^f_{y,x} < 2\Delta\) and setting \(f'_{x,y} = 0\) ensures that \(f_{x,y} - f'_{x,y} < 2\Delta\). Replacing \(f_{x,y}\) with \(f'_{x,y}\) therefore changes \(e_G\) by less than \(4\Delta\) once again.

Since we observed that \(e_G < 2\Delta n\) at the beginning of the \(\Delta\)-phase and there are \(m\) edges in \(G\) to which the initialization of the \(\Delta\)-phase may assign a flow \(f'_{x,y} \ne f_{x,y}\), we thus have \(e_G < 2\Delta n + 4\Delta m\) immediately after the initialization of the \(\Delta\)-phase.

Every flow augmentation in the \(\Delta\)-phase moves \(\delta \ge \Delta\) units of flow from an excess node \(s\) with \(e_s \ge \delta\) to a deficit node \(t\) with excess \(e_t \le -\delta\). Thus, it decreases \(e_G\) by \(2\delta \ge 2\Delta\). Since \(e_G < 2\Delta n + 4\Delta m\) after the initialization of the \(\Delta\)-phase, we therefore have \(e_G < 0\) after at most \(\frac{2\Delta n + 4\Delta m}{2\Delta} = n + 2m\) flow augmentations. Since \(e_G\) is easily seen to be non-negative at all times, this shows that each phase of the capacity scaling algorithm performs less than \(n + 2m\) flow augmentations. ▨

We have shown the following theorem:

Theorem 6.29: The capacity scaling algorithm takes \(O\bigl(\bigl(n^2 \lg n + nm\bigr)\lg U\bigr)\) time to compute a minimum-cost flow in a network whose vertices have integer supply balances between \(-U\) and \(U\) and whose edges have integral capacities.

Compare the capacity scaling algorithm to the successive shortest paths algorithm. The capacity scaling algorithm has to deal with some wrinkles when transitioning from one phase to the next because each phase ignores edges in the residual network with two low residual capacity. Beyond this minor complication, both algorithms are the same: they turn a pseudo-flow into a minimum-cost flow by repeatedly moving flow from excess nodes to deficit nodes. By restricting attention to node pairs with high excess and high deficit, and to paths between them with high residual capacity, at least initially, the capacity scaling algorithm is able to reduce the total number of flow augmentations to \(O((n + m)\lg U)\) whereas the successive shortest paths algorithm may perform \(O(nU)\) flow augmentations. This reduction in the number of flow augmentations is why the capacity scaling algorithm is faster than the successive shortest paths algorithm.

The scaling idea used in this section can also be applied to the edge costs instead of the edge capacities and even to both the edge costs and edge capacities. The cost scaling algorithm achieves a running time of \(O\bigl(n^3 \lg C\bigr)\), which is independent of the edge capacities and, assuming the graph is sufficiently dense and the edge costs are not too large, is faster than the capacity scaling algorithm. The double scaling algorithm, which applies scaling to both edge costs and edge capacities achieves a running time of \(O(nm \lg U \lg (nC))\), which is only little more than running Bellman-Ford's algorithm as long as the edge costs and capacities are polynomial in \(n\). For the details of these algorithm, see for example Sections 10.3 and 10.4 in Network Flows: Theory, Algorithms, and Applications. Instead of exploring these algorithms here, the remainder of this chapter focuses on minimum-cost flow algorithms whose running time is completely independent of the edge capacities and of the edge costs. These algorithms have the added benefit that they work for arbitrary real-valued edge costs and edge capacities. The next section shows how to obtain such an algorithm based on negative cycle cancelling, simply by choosing the negative cycles to cancel a little more carefully. Then we return to capacity scaling algorithms and show how to turn the \(\log U\) term in the running time of the algorithm we just discussed into a polylogarithmic term in \(n\). Note, however, that the independence of these algorithms from \(C\) and \(U\) is bought at the price of a substantially worse dependence on \(n\) and \(m\), and these algorithms are significantly more complicated. Thus, as long as the capacities or costs are integers and aren't astronomical, the algorithms discussed so far are almost always the better choice in practice.