Chapter 7

Network Flow

Slides by Kevin Wayne.

Copyright © 2005 Pearson-Addison Wesley.
All rights reserved.

1
Soviet Rail Network, 1955

Reference: On the history of the transportation and maximum flow problems.

Alexander Schrijver in Math Programming, 91: 3, 2002.

2
Maximum Flow and Minimum Cut

Max flow and min cut.

 Two very rich algorithmic problems.
 Cornerstone problems in combinatorial optimization.
 Beautiful mathematical duality.

Nontrivial applications / reductions.

 Data mining.  Network reliability.
 Open-pit mining.  Distributed computing.
 Project selection.  Egalitarian stable matching.
 Airline scheduling.  Security of statistical data.
 Bipartite matching.  Network intrusion detection.
 Baseball elimination.  Multi-camera scene reconstruction.
 Image segmentation.  Many many more …
 Network connectivity.

3
Minimum Cut Problem

Flow network.
 Abstraction for material flowing through the edges.
 G = (V, E) = directed graph, no parallel edges.
 Two distinguished nodes: s = source, t = sink.
 c(e) = capacity of edge e.

2 9 5

10 15 15 10
4

source s 5 3 8 6 10 t sink

4 6 15
15 10
capacity

4 30 7

4
Cuts

Def. An s-t cut is a partition (A, B) of V with s ∈ A and t ∈ B.

Def. The capacity of a cut (A, B) is: cap( A, B) = " c(e)

e out of A

2 9 5

10 15 15 10
4

s 5 3 8 6 10 t

4 6 15
15 10

Capacity = 10 + 5 + 15
4 30 7 = 30

5
Cuts

Def. An s-t cut is a partition (A, B) of V with s ∈ A and t ∈ B.

Def. The capacity of a cut (A, B) is: cap( A, B) = " c(e)

e out of A

2 9 5

10 15 15 10
4

s 5 3 8 6 10 t

A
4 6 15
15 10

Capacity = 9 + 15 + 8 + 30
4 30 7 = 62

6
Minimum Cut Problem

Min s-t cut problem. Find an s-t cut of minimum capacity.

2 9 5

10 15 15 10
4

s 5 3 8 6 10 t

4 6 15
A 15 10

Capacity = 10 + 8 + 10
4 30 7 = 28

7
Flows

Def. An s-t flow is a function that satisfies:

For each e ∈ E: 0 " f (e) " c(e) [capacity]
For each v ∈ V – {s, t}: " f (e) = " f (e) [conservation]
e in to v e out of v

Def. The value of a !flow f is: v( f ) = " f (e) .

e out of s
!
0
2 9 5
!
4 0
0
10 15 15 0 10
4 4

0 4 4
s 5 3 8 6 10 t

0 0
4 0 6 15 0
10
capacity 15
flow 0
0
Value = 4
4 30 7

8
Flows

Def. An s-t flow is a function that satisfies:

For each e ∈ E: 0 " f (e) " c(e) [capacity]
For each v ∈ V – {s, t}: " f (e) = " f (e) [conservation]
e in to v e out of v

Def. The value of a !flow f is: v( f ) = " f (e) .

e out of s
!
6
2 9 5
!
10 6
0
10 15 15 0 10
4 4

3 8 8
s 5 3 8 6 10 t

1 10
4 0 6 15 0
10
capacity 15
flow 11
11
Value = 24
4 30 7

9
Maximum Flow Problem

Max flow problem. Find s-t flow of maximum value.

9
2 9 5

10 9
1
10 15 15 0 10
4 0

4 8 9
s 5 3 8 6 10 t

4 10
4 0 6 15 0
10
capacity 15
flow 14
14
Value = 28
4 30 7

10
Flows and Cuts

Flow value lemma. Let f be any flow, and let (A, B) be any s-t cut.
Then, the net flow sent across the cut is equal to the amount leaving s.

" f (e) # " f (e) = v( f )

e out of A e in to A

! 6
2 9 5

10 6
0
10 15 15 0 10
4 4

3 8 8
s 5 3 8 6 10 t

A
1 10
4 0 6 15 0
15 10

11
11
Value = 24
4 30 7

11
Flows and Cuts

Flow value lemma. Let f be any flow, and let (A, B) be any s-t cut.
Then, the net flow sent across the cut is equal to the amount leaving s.

" f (e) # " f (e) = v( f )

e out of A e in to A

! 6
2 9 5

10 6
0
10 15 15 0 10
4 4

3 8 8
s 5 3 8 6 10 t

A
1 10
4 0 6 15 0
15 10

11
11 Value = 6 + 0 + 8 - 1 + 11
4 30 7 = 24

12
Flows and Cuts

Flow value lemma. Let f be any flow, and let (A, B) be any s-t cut.
Then, the net flow sent across the cut is equal to the amount leaving s.

" f (e) # " f (e) = v( f )

e out of A e in to A

! 6
2 9 5

10 6
0
10 15 15 0 10
4 4

3 8 8
s 5 3 8 6 10 t

A
1 10
4 0 6 15 0
15 10

11
11 Value = 10 - 4 + 8 - 0 + 10
4 30 7 = 24

13
Flows and Cuts

Flow value lemma. Let f be any flow, and let (A, B) be any s-t cut. Then

" f (e) # " f (e) = v( f ) .

e out of A e in to A

Pf. ! v( f ) = " f (e)

e out of s

% (
by flow conservation, all terms = " ' " f (e) $ " f (e)*
except v = s are 0 v # A & e out of v e in to v )

= " f (e) $ " f (e).

e out of A e in to A

14
Flows and Cuts

Weak duality. Let f be any flow, and let (A, B) be any s-t cut. Then the
value of the flow is at most the capacity of the cut.

Cut capacity = 30 ⇒ Flow value ≤ 30

2 9 5

10 15 15 10
4

s 5 3 8 6 10 t

4 6 15
15 10

Capacity = 30
4 30 7

15
Flows and Cuts

Weak duality. Let f be any flow. Then, for any s-t cut (A, B) we have
v(f) ≤ cap(A, B).

Pf.

A 4 B
v( f ) = " f (e) # " f (e) 8
e out of A e in to A t
$ " f (e)
e out of A
$ " c(e)
s
e out of A 7
= cap(A, B) ▪ 6

16
Certificate of Optimality

Corollary. Let f be any flow, and let (A, B) be any cut.

If v(f) = cap(A, B), then f is a max flow and (A, B) is a min cut.

Value of flow = 28
Cut capacity = 28 ⇒ Flow value ≤ 28

9
2 9 5

10 9
1
10 15 15 0 10
4 0

4 8 9
s 5 3 8 6 10 t

4 10
A 4 0 6 15 0
15 10

14
14
4 30 7

17
Towards a Max Flow Algorithm

Greedy algorithm.
 Start with f(e) = 0 for all edge e ∈ E.
 Find an s-t path P where each edge has f(e) < c(e).
 Augment flow along path P.
 Repeat until you get stuck.

0 0
20 10

s 30 0 t

10 20
0 0 Flow value = 0
2

18
Towards a Max Flow Algorithm

Greedy algorithm.
 Start with f(e) = 0 for all edge e ∈ E.
 Find an s-t path P where each edge has f(e) < c(e).
 Augment flow along path P.
 Repeat until you get stuck.

20 X
0 0
20 10

s 30 X
0 20 t

10 20
0 X
0 20 Flow value = 20
2

19
Towards a Max Flow Algorithm

Greedy algorithm.
 Start with f(e) = 0 for all edge e ∈ E.
 Find an s-t path P where each edge has f(e) < c(e).
 Augment flow along path P.
 Repeat until you get stuck.
locally optimality ⇒ global optimality

1 1

20 0 20 10
20 10 20 10

s 30 20 t s 30 10 t

10 20 10 20
0 20 10 20
2 2
greedy = 20 opt = 30
20
Residual Graph

Original edge: e = (u, v) ∈ E. capacity

Flow f(e), capacity c(e).

u 17 v


6
flow

Residual edge.
 "Undo" flow sent. residual capacity
 e = (u, v) and eR = (v, u).
 Residual capacity: u 11 v

$c(e) " f (e) if e # E 6

c f (e) = % residual capacity
& f (e) if e R # E

Residual graph: Gf = (V, Ef ).

!
 Residual edges with positive residual capacity.
 Ef = {e : f(e) < c(e)} ∪ {eR : f(e) > 0}.

21
Ford-Fulkerson Algorithm

2 4 4
capacity
G:
10 2 8 6 10

s 10 3 9 5 10 t

22
Augmenting Path Algorithm

Augment(f, c, P) {
b ← bottleneck(P)
foreach e ∈ P {
if (e ∈ E) f(e) ← f(e) + b forward edge
else f(eR)← f(eR) - b reverse edge
}
return f
}

Ford-Fulkerson(G, s, t, c) {
foreach e ∈ E f(e) ← 0
Gf ← residual graph

while (there exists augmenting path P) {

f ← Augment(f, c, P)
update Gf
}
return f
}

23
Max-Flow Min-Cut Theorem

Augmenting path theorem. Flow f is a max flow iff there are no

augmenting paths.

Max-flow min-cut theorem. [Elias-Feinstein-Shannon 1956, Ford-Fulkerson 1956]

The value of the max flow is equal to the value of the min cut.

Pf. We prove both simultaneously by showing TFAE:

(i) There exists a cut (A, B) such that v(f) = cap(A, B).
(ii) Flow f is a max flow.
(iii) There is no augmenting path relative to f.

(i) ⇒ (ii) This was the corollary to weak duality lemma.

(ii) ⇒ (iii) We show contrapositive.

 Let f be a flow. If there exists an augmenting path, then we can
improve f by sending flow along path.

24
Proof of Max-Flow Min-Cut Theorem

(iii) ⇒ (i)
 Let f be a flow with no augmenting paths.
 Let A be set of vertices reachable from s in residual graph.
 By definition of A, s ∈ A.
 By definition of f, t ∉ A.

v( f ) = " f (e) # " f (e)

e out of A e in to A A B
= " c(e)
e out of A t
= cap(A, B)

original network

25
Running Time

Assumption. All capacities are integers between 1 and C.

Invariant. Every flow value f(e) and every residual capacity cf (e)
remains an integer throughout the algorithm.

Theorem. The algorithm terminates in at most v(f*) ≤ nC iterations.

Pf. Each augmentation increase value by at least 1. ▪

Corollary. If C = 1, Ford-Fulkerson runs in O(mn) time.

Integrality theorem. If all capacities are integers, then there exists a

max flow f for which every flow value f(e) is an integer.
Pf. Since algorithm terminates, theorem follows from invariant. ▪

26
7.3 Choosing Good Augmenting Paths
Ford-Fulkerson: Exponential Number of Augmentations

Q. Is generic Ford-Fulkerson algorithm polynomial in input size?

m, n, and log C

A. No. If max capacity is C, then algorithm can take C iterations.

1 1

1 X
0 0 1 X
0 X
0 1
C C C C

s 1 X
0 1 t s 1 X
0 X
1 0 t

C C C C
0 X
0 1 1 X
0 X
0 1
2 2

28
Choosing Good Augmenting Paths

Use care when selecting augmenting paths.

 Some choices lead to exponential algorithms.
 Clever choices lead to polynomial algorithms.
 If capacities are irrational, algorithm not guaranteed to terminate!

Goal: choose augmenting paths so that:

 Can find augmenting paths efficiently.
 Few iterations.

Choose augmenting paths with: [Edmonds-Karp 1972, Dinitz 1970]

 Max bottleneck capacity.
 Sufficiently large bottleneck capacity.
 Fewest number of edges.

29
Capacity Scaling

Intuition. Choosing path with highest bottleneck capacity increases

flow by max possible amount.
 Don't worry about finding exact highest bottleneck path.
 Maintain scaling parameter Δ.
 Let Gf (Δ) be the subgraph of the residual graph consisting of only
arcs with capacity at least Δ.

4 4

110 102 110 102

s 1 t s t

122 170 122 170

2 2

Gf Gf (100)

30
Capacity Scaling

Scaling-Max-Flow(G, s, t, c) {
foreach e ∈ E f(e) ← 0
Δ ← smallest power of 2 greater than or equal to C
Gf ← residual graph

while (Δ ≥ 1) {
Gf(Δ) ← Δ-residual graph
while (there exists augmenting path P in Gf(Δ)) {
f ← augment(f, c, P)
update Gf(Δ)
}
Δ ← Δ / 2
}
return f
}

31
Capacity Scaling: Correctness

Assumption. All edge capacities are integers between 1 and C.

Integrality invariant. All flow and residual capacity values are integral.

Correctness. If the algorithm terminates, then f is a max flow.

Pf.
 By integrality invariant, when Δ = 1 ⇒ Gf(Δ) = Gf.
 Upon termination of Δ = 1 phase, there are no augmenting paths. ▪

32
Capacity Scaling: Running Time

Lemma 1. The outer while loop repeats 1 + log2 C times.

Pf. Initially C ≤ Δ < 2C. Δ decreases by a factor of 2 each iteration. ▪

Lemma 2. Let f be the flow at the end of a Δ-scaling phase. Then the
value of the maximum flow is at most v(f) + m Δ. proof on next slide

Lemma 3. There are at most 2m augmentations per scaling phase.

 Let f be the flow at the end of the previous scaling phase.
 L2 ⇒ v(f*) ≤ v(f) + m (2Δ).
 Each augmentation in a Δ-phase increases v(f) by at least Δ. ▪

Theorem. The scaling max-flow algorithm finds a max flow in O(m log C)
augmentations. It can be implemented to run in O(m2 log C) time. ▪

33
Capacity Scaling: Running Time

Lemma 2. Let f be the flow at the end of a Δ-scaling phase. Then value
of the maximum flow is at most v(f) + m Δ.
Pf. (almost identical to proof of max-flow min-cut theorem)
 We show that at the end of a Δ-phase, there exists a cut (A, B)
such that cap(A, B) ≤ v(f) + m Δ.
 Choose A to be the set of nodes reachable from s in Gf(Δ).
 By definition of A, s ∈ A.
 By definition of f, t ∉ A.

A B
v( f ) = " f (e) # " f (e)
e out of A e in to A t
$ " (c(e) # %) # " %
e out of A e in to A
= " c(e) # " % # "%
s
e out of A e out of A e in to A
$ cap(A, B) - m%

original network

34
!