1
Chapter 7
Network Flow
Slides by Kevin Wayne.
Copyright © 2005 Pearson-Addison Wesley.
All rights reserved.
1
Chapter 7
Network Flow
Slides by Kevin Wayne.
Copyright © 2005 Pearson-Addison Wesley.
All rights reserved.
2
Soviet Rail Network, 1955
Reference:
On the history of the transportation and maximum flow problems
.
Alexander Schrijver in Math Programming, 91: 3, 2002.
3
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.
ï®
Open-pit mining.
ï®
Project selection.
ï®
Airline scheduling.
ï®
Bipartite matching.
ï®
Baseball elimination.
ï®
Image segmentation.
ï®
Network connectivity.
ï®
Network reliability.
ï®
Distributed computing.
ï®
Egalitarian stable matching.
ï®
Security of statistical data.
ï®
Network intrusion detection.
ï®
Multi-camera scene reconstruction.
ï®
Many many more …
4
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.
Minimum Cut Problem
s
2
3
4
5
6
7
t
15
5
30
15
10
8
15
9
6
10
10
10
15
4
4
capacity
source
sink
5
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:
Cuts
s
2
3
4
5
6
7
t
15
5
30
15
10
8
15
9
6
10
10
10
15
4
4
Capacity = 10 + 5 + 15
= 30
A
!
cap
(
A
,
B
)
=
c
(
e
)
e
out of
A
"
6
s
2
3
4
5
6
7
t
15
5
30
15
10
8
15
9
6
10
10
10
15
4
4
A
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
"
Capacity = 9 + 15 + 8 + 30
= 62
7
Min s-t cut problem.
Find an s-t cut of minimum capacity.
Minimum Cut Problem
s
2
3
4
5
6
7
t
15
5
30
15
10
8
15
9
6
10
10
10
15
4
4
A
Capacity = 10 + 8 + 10
= 28
8
Def.
An
s-t flow
is a function that satisfies:
ï®
For each e
∈
E:
[capacity]
ï®
For each v
∈
V – {s, t}:
[conservation]
Def.
The
value
of a flow f is:
Flows
4
0
0
0
0
0
0
4
4
0
0
0
Value = 4
0
!
f
(
e
)
e
in to
v
"
=
f
(
e
)
e
out of
v
"
!
0
"
f
(
e
)
"
c
(
e
)
capacity
flow
s
2
3
4
5
6
7
t
15
5
30
15
10
8
15
9
6
10
10
10
15
4
4
0
!
v
(
f
)
=
f
(
e
)
e
out of
s
"
.
4
9
Def.
An
s-t flow
is a function that satisfies:
ï®
For each e
∈
E:
[capacity]
ï®
For each v
∈
V – {s, t}:
[conservation]
Def.
The
value
of a flow f is:
Flows
10
6
6
11
1
10
3
8
8
0
0
0
11
capacity
flow
s
2
3
4
5
6
7
t
15
5
30
15
10
8
15
9
6
10
10
10
15
4
4
0
Value = 24
!
f
(
e
)
e
in to
v
"
=
f
(
e
)
e
out of
v
"
!
0
"
f
(
e
)
"
c
(
e
)
!
v
(
f
)
=
f
(
e
)
e
out of
s
"
.
4
10
Max flow problem.
Find s-t flow of maximum value.
Maximum Flow Problem
10
9
9
14
4
10
4
8
9
1
0
0
0
14
capacity
flow
s
2
3
4
5
6
7
t
15
5
30
15
10
8
15
9
6
10
10
10
15
4
4
0
Value = 28
11
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.
Flows and Cuts
10
6
6
11
1
10
3
8
8
0
0
0
11
s
2
3
4
5
6
7
t
15
5
30
15
10
8
15
9
6
10
10
10
15
4
4
0
Value = 24
!
f
(
e
)
e
out of
A
"
#
f
(
e
)
e
in to A
"
=
v
(
f
)
4
A
12
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.
Flows and Cuts
10
6
6
1
10
3
8
8
0
0
0
11
s
2
3
4
5
6
7
t
15
5
30
15
10
8
15
9
6
10
10
10
15
4
4
0
!
f
(
e
)
e
out of
A
"
#
f
(
e
)
e
in to A
"
=
v
(
f
)
Value = 6 + 0 + 8 - 1 + 11
= 24
4
11
A
13
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.
Flows and Cuts
10
6
6
11
1
10
3
8
8
0
0
0
11
s
2
3
4
5
6
7
t
15
5
30
15
10
8
15
9
6
10
10
10
15
4
4
0
!
f
(
e
)
e
out of
A
"
#
f
(
e
)
e
in to A
"
=
v
(
f
)
Value = 10 - 4 + 8 - 0 + 10
= 24
4
A
14
Flows and Cuts
Flow value lemma.
Let f be any flow, and let (A, B) be any s-t cut. Then
Pf.
!
f
(
e
)
e
out of
A
"
#
f
(
e
)
=
v
(
f
)
e
in to
A
"
.
!
v
(
f
)
=
f
(
e
)
e
out of
s
"
=
v
#
A
"
f
(
e
)
e
out of
v
"
$
f
(
e
)
e
in to v
"
%
&
'
(
)
*
=
f
(
e
)
e
out of
A
"
$
f
(
e
).
e
in to A
"
by flow conservation, all terms
except v = s are 0
15
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
s
2
3
4
5
6
7
t
15
5
30
15
10
8
15
9
6
10
10
10
15
4
4
Capacity = 30
A
16
Weak duality.
Let f be any flow. Then, for any s-t cut (A, B) we have
v(f)
≤
cap(A, B).
Pf.
â–ª
Flows and Cuts
!
v
(
f
)
=
f
(
e
)
e
out of
A
"
#
f
(
e
)
e
in to
A
"
$
f
(
e
)
e
out of
A
"
$
c
(
e
)
e
out of
A
"
=
cap(
A
,
B
)
s
t
A
B
7
6
8
4
17
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
10
9
9
14
4
10
4
8
9
1
0
0
0
14
s
2
3
4
5
6
7
t
15
5
30
15
10
8
15
9
6
10
10
10
15
4
4
0
A
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.
s
1
2
t
10
10
0
0
0
0
0
20
20
30
Flow value = 0
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.
s
1
2
t
20
Flow value = 20
10
10
20
30
0
0
0
0
0
X
X
X
20
20
20
20
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
.
greedy = 20
s
1
2
t
20
10
10
20
30
20
0
0
20
20
opt = 30
s
1
2
t
20
10
10
20
30
20
10
10
10
20
locally optimality
⇒
global optimality
21
Residual Graph
Original edge:
e = (u, v)
∈
E.
ï®
Flow f(e), capacity c(e).
Residual edge.
ï®
"Undo" flow sent.
ï®
e = (u, v) and e
R
= (v, u).
ï®
Residual capacity:
Residual graph:
G
f
= (V, E
f
).
ï®
Residual edges with positive residual capacity.
ï®
E
f
= {e : f(e) < c(e)}
∪
{e
R
: f(e) > 0}.
u
v
17
6
capacity
u
v
11
residual capacity
6
residual capacity
flow
!
c
f
(e)
=
c(e)
"
f (e) if e
#
E
f (e)
if e
R
#
E
$
%
&
22
Ford-Fulkerson Algorithm
s
2
3
4
5
t
10
10
9
8
4
10
10
6
2
G:
capacity
23
Augmenting Path Algorithm
Augment(f, c, P) {
b
â†
bottleneck(P)
foreach
e
∈
P {
if
(e
∈
E) f(e)
â†
f(e) + b
else
f(e
R
)
â†
f(e
R
) - b
}
return
f
}
Ford-Fulkerson(G, s, t, c) {
foreach
e
∈
E f(e)
â†
0
G
f
â†
residual graph
while
(there exists augmenting path P) {
f
â†
Augment(f, c, P)
update G
f
}
return
f
}
forward edge
reverse edge
24
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.
25
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
)
e
out of
A
"
#
f
(
e
)
e
in to A
"
=
c
(
e
)
e
out of
A
"
=
cap
(
A
,
B
)
original network
s
t
A
B
26
Running Time
Assumption.
All capacities are integers between 1 and C.
Invariant.
Every flow value f(e) and every residual capacity c
f
(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.
â–ª
7.3 Choosing Good Augmenting Paths
28
Ford-Fulkerson: Exponential Number of Augmentations
Q.
Is generic Ford-Fulkerson algorithm polynomial in input size?
A.
No. If max capacity is C, then algorithm can take C iterations.
s
1
2
t
C
C
0
0
0
0
0
C
C
1
s
1
2
t
C
C
1
0
0
0
0
0
X
1
C
C
X
X
X
1
1
1
X
X
1
1
X
X
X
1
0
1
m, n, and log C
29
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.
30
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 G
f
(
Δ
) be the subgraph of the residual graph consisting of only
arcs with capacity at least
Δ
.
110
s
4
2
t
1
170
102
122
G
f
110
s
4
2
t
170
102
122
G
f
(100)
31
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
G
f
â†
residual graph
while
(
Δ
≥
1) {
G
f
(
Δ
)
â†
Δ
-residual graph
while
(there exists augmenting path P in G
f
(
Δ
)) {
f
â†
augment(f, c, P)
update G
f
(
Δ
)
}
Δ
â†
Δ
/ 2
}
return
f
}
32
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
⇒
G
f
(
Δ
) = G
f
.
ï®
Upon termination of
Δ
= 1 phase, there are no augmenting paths.
â–ª
33
Capacity Scaling: Running Time
Lemma 1.
The outer while loop repeats 1 +

log
2
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
Δ
.
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(m
2
log C) time.
â–ª
proof on next slide
34
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 G
f
(
Δ
).
ï®
By definition of A, s
∈
A.
ï®
By definition of f, t
∉
A.
!
v
(
f
)
=
f
(
e
)
e
out of
A
"
#
f
(
e
)
e
in to A
"
$
(
c
(
e
)
e
out of
A
"
# %
)
#
%
e
in to
A
"
=
c
(
e
)
e
out of
A
"
#
%
e
out of
A
"
#
%
e
in to
A
"
$
cap(A
,
B) - m
%
original network
s
t
A
B