6.8.4. Algorithm Overview

We are now ready to give a complete description of the repeated capacity scaling algorithm:

• Step 1: Compute an optimal potential function

  • We run the capacity scaling algorithm on \(G\) until we either obtain an optimal potential function \(\pi\) (along with an optimal flow \(f\)) or we discover an edge \((x, y)\) during some \(\Delta\)-phase whose current flow amount \(f_{x,y}\) satisfies \(f_{x,y} \ge 4\Delta\).

  • If we find an optimal potential function, we return it.

  • If we discover an edge \((x,y)\) with \(f_{x,y} \ge 4\Delta\), then let \(\pi\) be the current potential function at the time we discover this edge. We construct a new graph \(G''\) as follows:

    • First we construct a graph \(G'\) from \(G\) by assigning a cost \(c'_{w,z} = c^\pi_{w,z}\) to every edge \((w,z)\) in \(G\). The vertex supply balances remain unchanged and all edges remain uncapacitated.

    • We construct \(G''\) from \(G'\) by contracting the edge \((x,y)\): We remove the edge \((x,y)\) and replace the two vertices \(x\) and \(y\) with a single vertex \(z\). We replace every edge \((v,w)\) in \(G'\) such that \(w \in \{x, y\}\) with the edge \((v,z)\) in \(G''\). The cost of \((v,z)\) is the same as the cost of \((v,w)\). All edges in \(G''\) are once again uncapacitated. The supply balance of every vertex \(v \ne z\) in \(G''\) is the same as in \(G'\). The supply balance of \(z\) is \(b_x + b_y\), the combined balance of \(x\) and \(y\).

  • Given \(G''\), we invoke Step 1 recursively on \(G''\) to obtain an optimal potential function \(\pi''\) for \(G''\).

  • We convert this potential function \(\pi''\) into a potential function \(\pi'\) for \(G'\) by setting \(\pi'_v = \pi''_v\) for all \(v \notin \{x,y\}\) and \(\pi'_x = \pi'_y = \pi''_z\).

  • Finally, we obtain an optimal potential function for \(G\) as \(\pi' + \pi\). (Or at least, we claim that this is an optimal potential function for \(G\).)

• Step 2: Compute a minimum-cost flow

  • Given an optimal potential function for \(G\), we use Lemma 6.43 to convert it into a minimum-cost flow.

The correctness of Step 2 is established by Lemma 6.43. Thus, we only need to establish the correctness of Step 1. Most of the work to do this is also already done: Given an optimal potential function \(\pi'\) for \(G'\), Lemma 6.48 shows that \(\pi' + \pi\) is indeed an optimal potential function for \(G\). What we do need to show is that

• There even exists a feasible flow in \(G''\) (without which we cannot compute an optimal potential function for \(G''\) because this concept isn't even defined if there is no feasible flow), and

• If \(\pi''\) is an optimal potential function for \(G''\), then \(\pi'\) is an optimal potential function for \(G''\).

This is what we do in the next section.