# 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 innerwhileloop 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)$.