26-5 Maximum flow by scaling

Let $G = (V, E)$ be a flow network with source $s$, sink $t$, and an integer capacity $c(u, v)$ on each edge $(u, v) \in E$. Let $C = \max_{(u, v) \in E} c(u, v)$.

a. Argue that a minimum cut of $G$ has capacity at most $C|E|$.

b. For a given number $K$, show how to find an augmenting path of capacity at least $K$ in $O(E)$ time, if such a path exists.

We can use the following modification of $\text{FORD-FULKERSON-METHOD}$ to compute a maximum flow in $G$:

1
2
3
4
5
6
7
8
MAX-FLOW-BY-SCALING(G, s, t)
    C = max_{(u, v)  E} c(u, v)
    initialize flow f to 0
    K = 2^{floor(lg C)}
    while K  1
        while there exists an augmenting path p of capacity at least K augment flow f along p
        K = K / 2
    return f

c. Argue that $\text{MAX-FLOW-BY-SCALING}$ returns a maximum flow.

d. Show that the capacity of a minimum cut of the residual network $G_f$ is at most $2K|E|$ each time line 4 is executed.

e. Argue that the inner while loop of lines 5–6 executes $O(E)$ times for each value of $K$.

f. Conclude that $\text{MAX-FLOW-BY-SCALING}$ can be implemented so that it runs in $O(E^2\lg C)$ time.

a. The capacity of a cut is defined to be the sum of the capacities of the edges crossing it. Since the number of such edges is at most $|E|$, and the capacity of each edge is at most $C$, the capacity of any cut of $G$ is at most $C|E|$.

b. The capacity of an augmenting path is the minimum capacity of any edge on the path, so we are looking for an augmenting path whose edges all have capacity at least $K$. Do a breadth-first search or depth-first-search as usual to find the path, considering only edges with residual capacity at least $K$. (Treat lower-capacity edges as though they don't exist.) This search takes $O(V + E) = O(E)$ time. (Note that $|V| = O(E)$ in a flow network.)

c. $\text{MAX-FLOW-BY-SCALING}$ uses the Ford-Fulkerson method. It repeatedly augments the flow along an augmenting path until there are no augmenting paths with capacity at least $1$. Since all the capacities are integers, and the capacity of an augmenting path is positive, when there are no augmenting paths with capacity at least $1$, there must be no augmenting paths whatsoever in the residual network. Thus, by the max-flow min-cut theorem, $\text{MAX-FLOW-BY-SCALING}$ returns a maximum flow.

d.

  • The first time line 4 is executed, the capacity of any edge in $G_f$ equals its capacity in G, and by part (a) the capacity of a minimum cut of $G$ is at most $C|E|$. Initially $K = 2^{\lfloor \lg C \rfloor}$, and so $2K = 2 \cdot 2^{\lfloor \lg C \rfloor + 1} > 2^{\lg C} = C$. Thus, the capacity of a minimum cut of $G_f$ is initially less than $2K|E|$.
  • The other times line 4 is executed, $K$ has just been halved, and so the capacity of a cut of $G_f$ is at most $2K|E|$ at line 4 if and only if that capacity was at most $K|E|$ when the while loop of lines 5–6 last terminated. Thus, we want to show that when line 7 is reached, the capacity of a minimum cut of $G_f$ is at most $K|E|$.

Let $G_f$ be the residual network when line 7 is reached. When we reach line 7, $G_f$ contains no augmenting path with capacity at least $K$. Therefore, a maximum flow $f'$ in $G_f$ has value $|f'| < K|E|$. Then, by the max-flow min-cut theorem, a minimum cut in $G_f$ has capacity less than $K|E|$.

e. By part (d), when line 4 is reached, the capacity of a minimum cut of $G_f$ is at most $2K|E|$, and thus the maximum flow in $G_f$ is at most $2K|E|$. The following lemma shows that the value of a maximum flow in $G$ equals the value of the current flow $f$ in $G$ plus the value of a maximum flow in $G_f$.

Lemma

Let $f$ be a flow in flow network $G$, and $f'$ be a maximum flow in the residual network $G_f$. Then $f \uparrow f'$ is a maximum flow in $G$.

Proof

By the max-flow min-cut theorem, $|f'| = c_f(S, T)$ for some cut $(S, T)$ of $G_f$, which is also a cut of $G$. By Lemma 26.4, $|f| = f(S, T)$. By Lemma 26.1, $f \uparrow f'$ is a flow in $G$ with value $|f \uparrow f'| = |f| + |f'|$. We will show that $|f| + |f'| = c(S, T)$ which, by the max-flow min-cut theorem, will prove that $f \uparrow f'$ is a maximum flow in $G$.

We have

$$ \begin{aligned} |f| + |f'| & = f(S, T) + c_f(S, T) \\ & = \Bigg( \sum_{u \in S} \sum_{v \in T} f(u, v) - \sum_{u \in S} \sum_{v \in T} f(v, u) \Bigg) + \sum_{u \in S} \sum_{v \in T} c_f(u, v) \\ & = \Bigg( \sum_{u \in S, v \in T} f(u, v) - \sum_{u \in S, v \in T} f(v, u) \Bigg) + \Bigg( \sum_{u \in S, v \in T, (u, v) \in E} c(u, v) - \sum_{u \in S, v \in T, (u, v) \in E} f(u, v) + \sum_{u \in S, v \in T, (v, u) \in E} f(v, u) \Bigg). \end{aligned} $$

Noting that $(u, v) \notin E$ implies $f(u, v) = 0$, we have that

$$\sum_{u \in S, v \in T} f(u, v) = \sum_{u \in S, v \in T, (u, v) \in E} f(u, v).$$

Similarly,

$$\sum_{u \in S, v \in T} f(v, u) = \sum_{u \in S, v \in T, (v, u) \in E} f(v, u).$$

Thus, the summations of $f(u, v)$ cancel each other out, as do the summations of $f(v, u)$. Therefore,

$$ \begin{aligned} |f| + |f'| & = \sum_{u \in S, v \in T, (u, v) \in E} c(u, v) \\ & = \sum_{u \in S} \sum_{v \in T} c(u, v) \\ & = c(S, T). \end{aligned} $$

By this lemma, we see that the value of a maximum flow in $G$ is at most $2K|E|$ more than the value of the current flow $f$ in $G$. Every time the inner while loop finds an augmenting path of capacity at least $K$, the flow in $G$ increases by at least $K$. Since the flow cannot increase by more than $2K|E|$, the loop executes at most $(2K|E|) / K = 2|E|$ times.

f. The time complexity is dominated by the while loop of lines 4–7. (The lines outside the loop take $O(E)$ time.) The outer while loop executes $O(\lg C)$ times, since $K$ is initially $O(C)$ and is halved on each iteration, until $K < 1$. By part (e), the inner while loop executes $O(E)$ times for each value of $K$, and by part (b), each iteration takes $O(E)$ time. Thus, the total time is $O(E^2 \lg C)$.