7. NETWORK FLOW I
‣ max-flow and min-cut problems ‣ Ford-Fulkerson algorithm
‣ max-flow min-cut theorem
‣ capacity-scaling algorithm
‣ shortest augmenting paths
‣ blocking-flow algorithm
‣ unit-capacity simple networks
Lecture slides by Kevin Wayne Copyright © 2005 Pearson-Addison Wesley Copyright © 2013 Kevin Wayne
http://www.cs.princeton.edu/~wayne/kleinberg-tardos
Last updated on Sep 8, 2013 6:40 AM
SECTION 7.1
7. NETWORK FLOW I
‣ max-flow and min-cut problems ‣ Ford-Fulkerson algorithm
‣ max-flow min-cut theorem
‣ capacity-scaling algorithm
‣ shortest augmenting paths
‣ blocking-flow algorithm
‣ unit-capacity simple networks
Vancouver i
Kamloops Edmonton Ottawa
250 → Toronto yo
is
Seattle
Kooy Billings
: to
not
Flow network
・Abstraction for material flowing through the edges. ・Digraph G = (V, E) with source s ∈ V and sink t ∈ V.
Nonnegative integer capacity c(e) for each e ∈ E.
capacity
no parallel edges no edge enters s no edge leaves t
9 4 15
15 10 s5 8 10t
10
15
4 6 15 10 16
3
Maximum flow problem
D・ef. An st-flow (flow) f is a function that satisfies:
・For each e ∈ E: 0 ≤ f(e) ≤ c(e) [capacity]
∑ f(e) = ∑ f(e)
For each v ∈ V – {s, t}: €
€
e in to v
e out of v
capacity
[flow conservation]
flow
5 / 9
inflow at v = outflow at v =
5 + 5 + 0 10 + 0
= 10 = 10
s 5 / 5
5 / 8
10 / 10
t
0 /4
0 / 15
v
0 / 15
0 /4
10 / 16
7
5 / 10
5 / 15
10 / 10
10 / 15
0 /6
10 / 10
Maximum flow problem
D・ef. An st-flow (flow) f 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) e in to v e out of v
v( f ) = Def. The value of a flow f is: val(f) =
€
∑ f (e) . eoutof s
€ €
5/ 9
[flow conservation]
s
5 + 10 + 10 = 25
5 / 5
5 / 8
10 / 10 t
0 /4
0 / 15
value =
10 / 16
0 /4
0 / 15
8
5 / 10
5 / 15
10 / 10
10 / 15
0 /6
10 / 10
Maximum flow problem
D・ef. An st-flow (flow) f 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) [flow conservation] e in to v e out of v
v( f ) = ∑ f (e) . Def. The value of a flow f is: val(f) =
eoutof s Max-flow problem. Find a flow of maximum value.
€
€ €
8/ 9
s
8 + 10 + 10 = 28
5 / 5
8 / 8
10 / 10 t
0 /4
0 / 15
value =
13 / 16
0 /4
0 / 15
9
8 / 10
2 / 15
10 / 10
13 / 15
3 /6
10 / 10
Minimum cut problem
Def. A st-cut (cut) is a partition (A, B) of the vertices with s ∈ A and t ∈ B. Def. Its capacity is the sum of the capacities of the edges from A to B.
€
cap(A,B) = ∑ c(e) e out of A
10
s5t 15
capacity = 10 + 5 + 15 = 30
4
Minimum cut problem
Def. A st-cut (cut) is a partition (A, B) of the vertices with s ∈ A and t ∈ B. Def. Its capacity is the sum of the capacities of the edges from A to B.
€
A
–
‘
e””n.
10 (y-
e’
e
”
cap(A,B) =
∑ c(e) e out of A
B
sn8t ‘
don’t count edges from B to A
capacity = 10 + 8 + 16 = 34
y ,
16Y’ l’
5
Minimum cut problem
Def. A st-cut (cut) is a partition (A, B) of the vertices with s ∈ A and t ∈ B. Def. Its capacity is the sum of the capacities of the edges from A to B.
CA, B)
t- . t t #
s8t A
10
cap(A,B) = ∑ c(e) e out of A
Min-cut problem. Find a cut of minimum capacity. €
10
v Ift E cap
“‘ for
all flows
capacity = 10 + 8 + 10 = 28
6
B
SECTION 7.1
7. NETWORK FLOW I
‣ max-flow and min-cut problems ‣ Ford-Fulkerson algorithm
‣ max-flow min-cut theorem
‣ capacity-scaling algorithm
‣ shortest augmenting paths
‣ blocking-flow algorithm
‣ unit-capacity simple networks
Towards a max-flow algorithm
Greedy algorithm.
・Start with f (e) = 0 for all edge e ∈ E.
・Find an st path P where each edge has f (e) < c(e). ・Augment flow along path P.
・Repeat until you get stuck.
network G
0/ 4
0 / 10
0 /8
0 / 10
s 0 / 10
0 / 9
0 / 10
value of flow
t 0
0 /2
0 / 6
flow
capacity
11
Towards a max-flow algorithm
Greedy algorithm.
・Start with f (e) = 0 for all edge e ∈ E.
・Find an st path P where each edge has f (e) < c(e). ・Augment flow along path P.
・Repeat until you get stuck.
flow
capacity
network G
0/ 4
s 0 / 10
0 / 9
0 / 10
value of flow
t 0
0 /2
0 / 6
11
0 / 10
0 /8
0 / 10
Towards a max-flow algorithm
Greedy algorithm.
・Start with f (e) = 0 for all edge e ∈ E.
・Find an st path P where each edge has f (e) < c(e). ・Augment flow along path P.
・Repeat until you get stuck.
network G
0/ 4
s 0 / 10
0 / 9
8
—0 / 10
t 0 + 8 = 8
0 /2
0 / 6
12
0 / 10
8
—0 / 10
8
—0 / 8
Towards a max-flow algorithm
Greedy algorithm.
・Start with f (e) = 0 for all edge e ∈ E.
・Find an st path P where each edge has f (e) < c(e). ・Augment flow along path P.
・Repeat until you get stuck.
network G
0/ 4
s 0 / 10
—
t 8 + 2 = 10
2 —0 / 2
0 / 6
2
G2IO
—8 / 10
0/ 9
13
0 / 10
10
—8 / 10
8 /8
Towards a max-flow algorithm
Greedy algorithm.
・Start with f (e) = 0 for all edge e ∈ E.
・Find an st path P where each edge has f (e) < c(e). ・Augment flow along path P.
・Repeat until you get stuck.
network G
0/ 4
s —0 / 10 —2 / 9
10 / 10
t 10 + 6 = 16
2 / 2
6 —0 / 6
68
14
6
—0 / 10
8 /8
10 / 10
Towards a max-flow algorithm
Greedy algorithm.
・Start with f (e) = 0 for all edge e ∈ E.
・Find an st path P where each edge has f (e) < c(e). ・Augment flow along path P.
・Repeat until you get stuck.
network G
ending flow value = 16
0/ 4
s 6 / 10
8 / 9
10 / 10
t 16
2 /2
6 / 6
15
6 / 10
8 /8
10 / 10
Towards a max-flow algorithm
Greedy algorithm.
・Start with f (e) = 0 for all edge e ∈ E.
・Find an st path P where each edge has f (e) < c(e). ・Augment flow along path P.
・Repeat until you get stuck.
but max-flow value = 19
network G
3/ 4
s 9 / 10
9 / 9
10 / 10
t 19
0 /2
6 / 6
16
9 / 10
7 /8
10 / 10
residual -Define
Vl
Towards a solution : the
graph
residual
graph
✓ ( Gf )
61
:= Forward edges :
f-(e) accel,
residual capacity cle ) - Hel
e = Curl sit. add e to Gf with
For edge
-Backward edges
,
Claim
If then
'
flow is a
graph
flow in the original graph
:
add
For
-
f
e ' - is a
f tf '
Hel 70 Chul to Gf with residual
capacity
f-let
edge e = Curl S.t.
i n
residual
Gf
, G.
Claim
Prout:
f
'
is a flow
graph
flow in the original graph
If
then ff' is a +
i n
residual
Gf
, G.
Suppose f ' is a flow in residual graph .
For any flow assigned to forward edge e ,
reside capacity ensures that f-Cel tf'let E Recall : O e f'let s cle ) - f- le )
⇒
c Cel.
J,
O E f-let+f'lets feeltale)- Hel= cle)
tresidcapacitt
Claim Prout:
If then
Suppose
f
'
is a f tf '
flow is a
graph
flow in the original graph
i n
residual
Gf
, G.
f ' is
a
flow in residual graph .
For any flow assigned to backward edge , w e only f flow of f
backward edge Recall that
⇒
fluid
) z - fluid
=o
(decreases no lower than o
( vial
r-esid capacity
oe
E
fluid tf'la, v1
f'(vial
flu id
f' v.
oz
H
-
( ul
Clum Z
Cvn
- z
-
-f' )
fluid
Residual graph
Original edge: e = (u, v) ∈ E. ・Flow f (e).
・Capacity c(e).
R・esidual edge.
・"Undo" flow sent. ・e = (u, v) and eR = (v, u).
Residual capacity:
cf(e)=$%c(e)−f(e) ife∈E &f(e) if eR ∈E
original graph G
u 6/17 v flow capacity
residual graph Gf
residual capacity
R・esidual graph: Gf = (V, Ef ).
€・Residual edges with positive residual capacity.
・E = {e : f (e) < c(e)} ∪ {eR : f (e) > 0}. f
where flow on a reverse edge negates flow on a forward edge
u 11 v 6
Key property: f ‘ is a flow in G iff f + f ‘ is a flow in G. f
17
Augmenting path
Def. An augmenting path is a simple st path P in the residual graph Gf . Def. The bottleneck capacity of an augmenting P is the minimum
residual capacity of any edge in P.
Key property. Let f be a flow and let P be an augmenting path in Gf .
Then f ‘ is a flow and val(f ‘) = val(f) + bottleneck(Gf, P). AUGMENT (f, c, P)
________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
b ← bottleneck capacity of path P. FOREACH edge e ∈ P
www.krlc-PEBTTT-yysgiforwardedgethenfu IF(e∈E) f(e) ← f(e) + b., v1 ←
tb IFENG.gs#ackgnedT7thenflv.ut-flr, u l
fluid ELSE If f(eR)←f(eR) – b.
-b
RETURN f. ________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
18
Ford-Fulkerson algorithm
F・ord-Fulkerson augmenting path algorithm.
・Start with f (e) = 0 for all edge e ∈ E.
・Find an augmenting path P in the residual graph G . f
・Augment flow along path P. Repeat until you get stuck.
FORD-FULKERSON (G, s, t, c) _________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
FOREACH edgee∈E:f(e)←0.
Gf ←residualgraph.
WHILE (there exists an augmenting path P in Gf )
f ← AUGMENT (f, c, P).
Update Gf. RETURN f.
} _________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
19
Ford-Fulkerson algorithm demo
network G
flow
capacity
0/ 6
0/ 4
s 0 / 10
residual graph Gf
0 / 9
0 / 10
value of flow t 0
0/ 2
4
residual capacity
26
s10 9 10t
20
10
0 / 10
0 / 10
10
0 /8
8
Ford-Fulkerson algorithm demo
network G
0/ 4
s 0 / 10
residual graph Gf
0 / 9
8
—0 / 10
t 0 + 8 = 8
0/ 2
0/ 6
4
26
s10 9 10t
21
10
8
—0 / 10
0 / 10
10
8
—0 / 8
8
Ford-Fulkerson algorithm demo
network G
0/ 4
s 0 / 10
residual graph Gf
22
— —8 / 10 0/ 9
t 8 + 2 = 10
2 —0 / 2
0 / 6
4
26
s10 9 2t 8
22
8
2
10
—8 / 10
0 / 10
10
8 /8
8
Ford-Fulkerson algorithm demo
network G
0/ 4
2 / 2
6 —0 / 6
68
s —0 / 10 — 2/ 9
10 / 10
t 10 + 6 = 16
residual graph Gf
4
26
s10 7 10t 2
23
10
10 / 10
6
—0 / 10
10
8 /8
8
Ford-Fulkerson algorithm demo
network G
2
—0 / 4
s —6 / 10
residual graph Gf
8 / 9
10 / 10
t 16 + 2 = 18
8
0 —2 / 2
6 / 6
4
26
s4 1 10t 68
24
10
10 / 10
8
—6 / 10
4
6
8 /8
8
Ford-Fulkerson algorithm demo
network G
3
—2 / 4
s —8 / 10 — 8/ 9
10 / 10
t 18 + 1 = 19
0/ 2
6/ 6
99
residual graph Gf
2
2
26
s2 1 10t 88
25
10
10 / 10
9
—8 / 10
2
8
7
—8 / 8
8
Ford-Fulkerson algorithm demo
network G
min cut
3/ 4
0/ 2
6/ 6
max flow
s 9 / 10
9 / 9
3
1
10 / 10
t 19
residual graph Gf
nodes reachable from s
26
s1 9 10t 9
26
10
10 / 10
9 / 10
1
9
7 /8
7 1
R-untime analysis of Ford – Fulkerson
( nonnegative integer) capacities
Assume
that
max
del E
claim
:
flow f
:
v
)
E
ECle)sCn-it. C e outofs
0(
any
C EEE
(f 5#o
– n
vertices
+ positive
integer
=
nc
)
Every
#
augmentation
augmentations
of flow along some path P M the flow by at least I
path t T( f .
=0() E(n-t)-C nc
( # iterations of white loop) Runtime = O m C ) finding a n
SECTION 7.2
7. NETWORK FLOW I
‣ max-flow and min-cut problems ‣ Ford-Fulkerson algorithm
‣ max-flow min-cut theorem
‣ capacity-scaling algorithm
‣ shortest augmenting paths
‣ blocking-flow algorithm
‣ unit-capacity simple networks
(- Analysis
cut B) Givenan s- t CA,
Correctness )
of Ford – Fulkerson
,
crossing originates
Algorithm
“outof ” ifitis A
Similarly -AB
“into
” if
it
edge for
edge (air)
(AIB)
,
we sat an edgee- 14N) is
a crossing edge for CA, B) that originates in A .
(so UEA and re B!
an
is
A isa
o÷¥⇒
(so uc-B vet) ,
that
i n
B
.
-Flow
Let
¥:#
lemma (AM be an
Value
:
t Then rift
=
E
–
E e into
s- cut
.
f le ) e outofA
Hel A
VH1 = E f- let b/c conservation of flow e out of s = 0
⇒
i¥”÷a” =Efk1-E
-‘
Ea
” :÷÷¥ –
tea :& : :
“”
—
.
re
e
? ! ?’
–
– ?!!”?
e
‘ .me?totrHet-rc?av.s,!.e?…vfH–rEae?utoFi
–
f. fin
” .
e outofA
e into A
Observation: Take A= VI Flow Value lemma :
‘s
B —
⇒ rfft =t
e
EHel= EtHel out of s e into
ft rift =
ttt .
E Hel –
E Definition
–
e outof Vlftt
E Hel
e into Vitti
=
e into t
Hel
Hel out of
e -E
t
-Weak
s- tcutCA,B) forany
Duality
f
( flow
For any ✓
flow
:
Max flows f
=
CAB
Ifl
Hel
A
=
E
out of A
e
e into
ZO
E
e
cle ) out ofA
Vlf)
s-
min capCA, B) t cuts
,
Hel – -E
Hel
value
lemma )
= E
E cap
( A. Bl
A
E
E
e outof
Definition
theorem
Proof : –
Algorithm
max
–
”
‘in”÷÷÷÷÷÷÷¥. = Cle)
Ford –
Fulkerson
Algorithm finds
flow
=
e
n o
augmenting path
oe÷Y
terminates (so,nos-t
augmenting path in Gf)
.
when n o
path in
Gf
create s t cut ( ‘ ‘t) where A* is set of vertices -AB
,
v sit.
path in Gf
At ?+.fr#lel=cdnCATB ‘T q
St
” B=VIA
‘t .
there is
s – v
1.
SEA * test b/c
2
Flow .
:*:*
1.
SEA *
test b/c n o augmenting
cannot exist → J,
” the
e
. :ni÷¥
= Cle)
( claim
–
=
Claim’ll: foranyedgee-Carlout
Gf ,
e
fatof a *
of A*
f-let =
del
It Cle )
( claim = cap
2) CA*,B*)
.
path oem÷
-Value lemma: mm,
( -=0
At
St
⇒A veA*)#
If , then in Gf we h*& have edge Cair not
claim 2 : for any edge e= ( ‘m’t u
k¥
‘m
#
pinto At, fle) = 0
If not, then in Gf we have backward edge (r ‘t ⇒ u ‘t tf
Max flows f
=
CAB
-Fulkerson
Ford- provides*
flow f (At ) s- t. Vlf)= cap ,B*
dnt →f
flow
,
✓ of
Vlf)
s-
min capCA, B) t cuts
f a
‘
(f
‘t e cap(AtB”) ,
Hou )
,B*l=vfH
flow
cat
(Air) ,
is a cat
value
(
max
is
maximum
Ford – Fulkerson
Any
s- t s- t cut
⇒ (Att,
cap A”
provides
CAT It ( .
cap (A.B) z VH1
of minimum capacity
(min cut)
-Baseball
Elimination
( Application )
4
hockey
Toronto Montreal
teams :
Leafs Canadiens
Canucks
Victoria Royals, ,
Montreal
There Question :
:
Toronto : 73 wins
Vancouver : 70 wins
Victoria : 72 wins
are
games
Vancouver be
, o n e eliminated
time, after the 6 games
Maple 72 wins
Vancouver ,
6 will
for each pair of
remaining
Vancouver has 3 games remaining Optimistically , Vancouver ‘ all .
3
w in s
7-2 t 73t 72 +3 = 220 7 73 wins ⇒ 3-T
one team >
⇒ 70+3
=73
w in s
complete.
.
must have 73 wins
a re
Relationship between flows and cuts
Flow value lemma. Let f be any flow and let (A, B) be any cut. Then, the net flow across (A, B) equals the value of f.
∑f(e) − ∑f(e) = v(f) e out of A e in to A
netflowacrosscut = 5+10+10= 25
s
5 / 5
5 / 8
10 / 10
t value of flow = 25
€
5/ 9
0 /4
0 / 15
0 /4
0 / 15
10 / 16
28
5 / 10
5 / 15
10 / 10
10 / 15
0 /6
10 / 10
Relationship between flows and cuts
Flow value lemma. Let f be any flow and let (A, B) be any cut. Then, the net flow across (A, B) equals the value of f.
∑f(e) − ∑f(e) = v(f) e out of A e in to A
netflowacrosscut = 10+5+10= 25
€
5/ 9
s
5 / 5
5 / 8
10 / 10
t value of flow = 25
0 /4
0 / 15
0 /4
0 / 15
10 / 16
29
5 / 10
5 / 15
10 / 10
10 / 15
0 /6
10 / 10
Relationship between flows and cuts
Flow value lemma. Let f be any flow and let (A, B) be any cut. Then, the net flow across (A, B) equals the value of f.
∑f(e) − ∑f(e) = v(f) e out of A e in to A
netflowacrosscut = (10+10 +5+10+0+0)–(5+5+0+0) = 25
s
5 / 5
5 / 8
10 / 10
€
5/ 9
0 /4
0 / 15
edges from B to A
t value of flow = 25
0 /4
0 / 15
10 / 16
30
5 / 10
5 / 15
10 / 10
10 / 15
0 /6
10 / 10
Relationship between flows and cuts
Flow value lemma. Let f be any flow and let (A, B) be any cut. Then, the net flow across (A, B) equals the value of f.
∑f(e) − ∑f(e) = v(f)
Pf.
€
v(f) v(f)
= =
∑ f(e) ∑ f(e)
by flow conservation, all terms except v = s are 0
%( %(
€ €
€
e out of A
e in to A
v(f)
=
∑ f(e) e out of s
= =
∑%∑f(e)−∑f(e)( ∑’∑f(e)−∑f(e)*
=
∑’∑f(e)−∑f(e)*
= =
e in to v ∑f(e)− ∑f(e).
=
∑f(e)− ∑f(e). ∑f(e)− ∑f(e).
▪
e out of s e out of s
‘&
v ∈A &e out of v
e in to v e in to v
*) )
v ∈A &e out of v v ∈ A e out of v
)
e out of A e out of A
e in to A e in to A
e out of A
e in to A
31
€
8 /9
7 / 8
12 / 16
Relationship between flows and cuts
Weak duality. Let f be any flow and (A, B) be any cut. Then, v( f ) ≤ cap(A, B).
Pf. v(f)
= ∑ f(e)− ∑ f(e)
v(f) v(f) v(f)
flow-value lemma
= ∑ f(e)− ∑ f(e) = ∑ f(e)− ∑ f(e) = eout∑ofAf(e)−ein∑toAf(e)
e out of A e out of A e out of A
e in to A e in to A e in to A
≤ ∑ f(e)
≤ ∑ f(e) ≤ ∑ f(e) ≤ e out∑of Af (e)
e out of A eoutofA e out of A
≤ ∑ c(e)
≤ ∑ c(e) ≤ ∑ c(e) ≤ e out∑of Ac(e)
e out of A e out of A e out of A
= cap(A,B)
= cap(A,B) = cap(A,B) = cap(A,B)
▪
10 9 / 10 t s 5
15
€ € €
0 /4
0 /4
0 / 15
0 / 15
s
5 /5
t
value of flow = 27
≤
capacity of cut = 30
32
8 / 10
2 / 15
10 / 10
12 / 15
2/ 6
10 / 10
Max-flow min-cut theorem
Augmenting path theorem. A flow f is a max-flow iff no augmenting paths. Max-flow min-cut theorem. Value of the max-flow = capacity of min-cut.
Pf. The following three conditions are equivalent for any flow f : i. There exists a cut (A, B) such that cap(A, B) = val(f ).
ii. f is a max-flow.
iii. There is no augmenting path with respect to f.
[ i ⇒ ii ]
・Suppose that (A, B) is a cut such that cap(A, B) = val(f ).
・Then, for any flow f ‘, val(f ‘) ≤ cap(A, B) = val(f ).
・Thus, f is a max-flow. ▪
weak duality by assumption
33
Max-flow min-cut theorem
Augmenting path theorem. A flow f is a max-flow iff no augmenting paths. Max-flow min-cut theorem. Value of the max-flow = capacity of min-cut.
Pf. The following three conditions are equivalent for any flow f : i. There exists a cut (A, B) such that cap(A, B) = val(f ).
ii. f is a max-flow.
iii. There is no augmenting path with respect to f.
[ ii ⇒ iii ] We prove contrapositive: ~iii ⇒ ~ii.
・Suppose that there is an augmenting path with respect to f. ・Can improve flow f by sending flow along this path. ・Thus, f is not a max-flow. ▪
34
Max-flow min-cut theorem
[・iii⇒i]
・Let f be a flow with no augmenting paths.
・Let A be set of nodes reachable from s in residual graph Gf. ・By definition of cut A, s ∈ A.
By definition of flow f, t ∉ A.
edge e = (v, w) with v ∈ B, w ∈ A must have f(e) = 0
B
v(f) = v(f) = v(f) =
= = = = = =
∑f(e)− ∑f(e) ∑f(e)− ∑f(e)
original network G
A
e out of A e in to A ∑f(e)− ∑f(e)
flow-value lemma
€ € €
e out of A
∑ c(e)
t
e out of A
∑ c(e)
e in to A e in to A
eoutofA
∑ c(e)
e out of A cap(A,B)
e out of A cap(A,B)
cap(A,B)
s
edge e = (v, w) with v ∈ A, w ∈ B must have f(e) = c(e)
35
SECTION 7.3
7. NETWORK FLOW I
‣ max-flow and min-cut problems ‣ Ford-Fulkerson algorithm
‣ max-flow min-cut theorem
‣ capacity-scaling algorithm
‣ shortest augmenting paths
‣ blocking-flow algorithm
‣ unit-capacity simple networks
Running time
Assumption. Capacities are integers between 1 and C.
Integrality invariant. Throughout the algorithm, the flow values f (e)
and the residual capacities cf (e) are integers.
Theorem. The algorithm terminates in at most val (f *) ≤ n C iterations.
Pf. Each augmentation increases the value by at least 1. ▪ Corollary. The running time of Ford-Fulkerson is O(m n C).
Corollary. If C = 1, the running time of Ford-Fulkerson is O(m n).
Integrality theorem. Then exists a max-flow f * for which every flow value f *(e) is an integer.
Pf. Since algorithm terminates, theorem follows from invariant. ▪
37
Bad case for Ford-Fulkerson
Q. Is generic Ford-Fulkerson algorithm poly-time in input size?
m, n, and log C
A. No. If max capacity is C, then algorithm can take ≥ C iterations.
・s→v→w→t
・s→w→v→t
each augmenting path sends only 1 unit of flow (# augmenting paths = 2C)
vCt
C1C
sCw
・s→v→w→t ・
・s→w→v→t ・…
・s→v→w→t s→w→v→t
38
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.
39
Choosing good augmenting paths
C・hoose augmenting paths with:
・Max bottleneck capacity. ・Sufficiently large bottleneck capacity.
Fewest number of edges.
Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
JACK EDMONDS
University of Waterloo, Waterloo, Ontario, Canada
AND
RICHARD M. KARP
University of California, Berkeley, California
ABSTRACT. This paper presents new algorithms for the maximum flow problem, the Hitchcock transportation problem, and the general minimum-cost flow problem. Upper bounds on the numbers of steps in these algorithms are derived, and are shown to compale favorably with upper bounds on the numbers of steps required by earlier algorithms.
First, the paper states the maximum flow problem, gives the Ford-Fulkerson labeling method
for its solution, and points out that an improper choice of flow augmenting paths can lead to
Edmonds-Karp 1972 (USA)
Dinic 1970 (Soviet Union)
severe computational difficulties. Then rules of choice that avoid these difficulties are given.
We show that, if each flow augmentation is made along an augmenting path having a minimum number of arcs, then a maximum flow in an n-node network will be obtained after no more than ~(na – n) augmentations; and then we show that if each flow change is chosen to produce a maximum increase in the flow value then, provided the capacities are integral, a maximum flow will be determined within at most 1 + logM/(M–1) if(t, S) augmentations, wheref*(t, s) is the value of the maximum flow and M is the maximum number of arcs across a cut.
Next a new algorithm is given for the minimum-cost flow problem, in which all shortest-path computations are performed on networks with all weights nonnegative. In particular, this algorithm solves the n X n assigmnent problem in O(n3)steps. Following that we explore a “scaling” technique for solving a minimum-cost flow problem by treating a sequence of derived problems with “scaled down” capacities. It is shown that, using this technique, the solution of a Iiitchcock transportation problem with m sources and n sinks, m ~ n, and maximum flow B, requires at most (n + 2) log2 (B/n) flow augmentations. Similar results are also given for the general minimum-cost flow problem.
40
An abstract stating the main results of the present paper was presented at the Calgary
International Conference on Combinatorial Structures and Their Applications, June 1969. In a paper by l)inic (1970) a result closely related to the main result of Section 1.2 is obtained.
Dinic shows that, in a network with n nodes and p arcs, a maximum flow can be computed in
Capacity-scaling algorithm
Intuition. Choose augmenting path with highest bottleneck capacity: it increases flow by max possible amount in given iteration.
・Don’t worry about finding exact highest bottleneck path.
・Maintain scaling parameter Δ.
・Let G (Δ) be the subgraph of the residual graph consisting only of f
arcs with capacity ≥ Δ. ss
1
tt
Gf Gf(Δ), Δ=100
41
110
170
110
170
102
122
102
122
Capacity-scaling algorithm
CAPACITY-SCALING(G, s, t, c) __________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
FOREACH edgee∈E:f(e)←0. Δ ← largest power of 2 ≤ C.
WHILE (Δ ≥ 1)
Gf (Δ) ← Δ-residual graph.
WHILE (there exists an augmenting path P in Gf (Δ))
f ← AUGMENT (f, c, P).
Update Gf (Δ). Δ ← Δ / 2.
RETURN f. __________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
42
Capacity-scaling algorithm: proof of correctness
Assumption. All edge capacities are integers between 1 and C. Integrality invariant. All flow and residual capacity values are integral.
Theorem. If capacity-scaling algorithm terminates, then f is a max-flow. Pf.
・By integrality invariant, when Δ = 1 ⇒ G (Δ) = G . ff
・Upon termination of Δ = 1 phase, there are no augmenting paths. ▪
43
Capacity-scaling algorithm: analysis of running time
Lemma 1. The outer while loop repeats 1 + ‘log2 C( times.
Pf. Initially C / 2 < Δ ≤ C; Δ decreases by a factor of 2 in each iteration. ▪
Lemma 2. Let f be the flow at the end of a Δ-scaling phase. Then,
the value of the max-flow ≤ val(f) + m Δ.
proof on next slide
Lemma 3. There are at most 2m augmentations per scaling phase. P・f.
・Let f be the flow at the end of the previous scaling phase. ・LEMMA 2 ⇒ val( f *) ≤ val( f ) + 2 m Δ .
Each augmentation in a Δ-phase increases val( 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.
Pf. Follows from LEMMA 1 and LEMMA 3. ▪
44
Capacity-scaling algorithm: analysis of running time
Lemma 2. Let f be the flow at the end of a Δ-scaling phase. Then, the value of the max-flow ≤ val(f) + m Δ.
P・f.
・We show there exists a cut (A, B) such that cap(A, B) ≤ val(f) + m Δ. ・Choose A to be the set of nodes reachable from s in G (Δ).
・By definition of cut A, s ∈ A. By definition of flow f, t ∉ A.
f
edge e = (v, w) with v ∈ B, w ∈ A
val(f) v(f) =
v(f) =
v(f) = ≥ v(f) = ≥
≥ = ≥ =
= ≥ = ≥
≥ ≥
∑ f(e)− ∑ f(e)
eout∑ofAf(e) −ein∑toAf(e)
original network
A
must have f(e) ≤ Δ
B
eout∑ofAf(e) −ein∑toAf(e)
∑(c(e)−Δ)−∑Δ
∑ f(e)− ∑ f(e) e out of A e in to A
t
eout∑ofA(c(e)−Δ) −ein∑toA Δ
e out of A e in to A
eout∑ofA(c(e)−Δ) −ein∑toA Δ
∑c(e)−∑Δ−∑Δ
∑(c(e)−Δ)−∑Δ e out of A e in to A
eout∑ofAc(e)−eou∑tofAΔ−ein∑toAΔ e out of A e in to A
eout∑ofAc(e)−eou∑tofAΔ−ein∑toAΔ cap(A, B) - mΔ
s
∑c(e)−∑Δ−∑Δ e out of A e out of A e in to A
cap(A, B) - mΔ
e out of A e out of A e in to A cap(A, B) - mΔ
cap(A, B) - mΔ
edge e = (v, w) with v ∈ A, w ∈ B must have f(e) ≥ c(e) – Δ
45
SECTION 17.2
7. NETWORK FLOW I
‣ max-flow and min-cut problems ‣ Ford-Fulkerson algorithm
‣ max-flow min-cut theorem
‣ capacity-scaling algorithm
‣ shortest augmenting paths
‣ blocking-flow algorithm
‣ unit-capacity simple networks
Shortest augmenting path
Q. Which augmenting path?
A. The one with the fewest number of edges.
can find via BFS
SHORTEST-AUGMENTING-PATH(G, s, t, c) _________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
FOREACH e∈E:f(e)←0.
Gf ←residualgraph.
WHILE (there exists an augmenting path in Gf )
P ← BREADTH-FIRST-SEARCH (Gf, s, t). f ← AUGMENT (f, c, P).
Update Gf.
RETURN f. _________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
47
For flow f and vertex v, let !f (s, v) be length of shortest s-v path in Gf (“shortest” means least number of edges)
Lemma
If Edmonds-Karp is run on a flow network, then throughout the algorithm, for all vertices v ! V !{s, t}, the shortest path distance !f (s, v) never
decreases.
Proof
Let f be the flow just prior to first augmentation that decreases some (shortest path) distance, and let f! be the next flow
Among all vertices whose distance decreases from Gf to Gf! , let v be the vertex with minimum !f!(s, v)
Let P be shortest s-v p-ath in G , and let u be predecessor of v in P f!
(Siu) < ffi(Sir) ⇒ ff. (Siu) Z ff(s, a) ,
5me1→4 (3)
Afteraugmentation: 5runs@→2 ,
PispathinGf
Cl) Sf, (s Vl = ff, (salt ,
1
Because
In Claim
shortest Sf
path
claim :
⇒
s -
ff Gf
( 2)
,
a (s,ul
=
is of the form Sf (Sir) t I
Proof continued
Cl ) Sf, ( Slv) = ff, ( salt
1
Because
Sf , Gf
Sf
ff(s,
( 2) @→ 4
(3)
at
In Claim
shortests-apathisoftheform5me ,
Sf (Siv) t I
ell
claim :
⇒
(s,at
=
(Siu) < ffi(Slv ) ⇒ ff. (Siu) Z
a )
Sf ,
Is
=
Sf ,
Z
ff ,
shortest
path v
dist . actually
.
Is, ul H
(S, v1
tf
f
=Sf, + from
ul
Isr)z ← to
IT (3)
S
increased by 2
Proof continued
In Prout
Gf
shortests-apathisoftheform5me ,
@→ 4
Claim :
first Suppose
claims
(UN) is not an
edge in Gf
we ,
.
( for
that Girl is
Gf
edge in
(s, v1 E Sf(s, ul t l (triangle inequality)
contradiction )
.
( Sf
CZ)
E
Is ,rl
luv) is not in Gf But ! (un is .
b in
ffi
(S, u ) tt
=
ff,
CH
.
Indeed
,
Gf'
augmented in Gf
⇒ Chul belongs Ito the path along which flow was
.
edge in s ⇒ (Yul is .
p
from S toa.
.
-Theorem
If Edmonds-Karp is run on a flow network, then the algorithm performs
O(mn) flow augmentations.
o_0 L2
m=
#edges n = # vertices
froot
so:÷÷.
shortest path,
lot Lz
P = ( Vo , Y . . . . , .
let
At After
P plc
ti :
E Li bottleneck
be
to
augmenting path sit
V;
)
P least
is a
Vi
o f
( vii. Vital edge in
"
augmentation flow uses all of
crit, ,q,
L,
inn Gf
" - augment: (vi.vital is removed! and we addbackwardedge
o n e
P
will be
edge
this edge; residual capacity.
let
At After
P
least
( vii. Vital edge in
P
will be
bottleneck
edge
augmentation flow uses all of
crit, ,q. )
inn Gf augmenting path sit
P = ( Vo , Y . . . . , .
be
plc fis a Shor tpath,
o n e augment:
this edge; residual capacity.
V; )
" - (vi.vital is removed! and we addbackwardedge
Suppose that later , in some
⇒ (Viti , Vi) belongs to shortest s- t
ff, (s,Vil=
Sf(s, Vin)H
(s, Vil t 2
vi. via ) after
Sf, (s,
Viti) H
ti: ViE Li "
o f
n e w
,
residual graph Gf '
the edge ( comes back
flow in path
Gfl.
in
augment Gfi .
Z =
Sf
Each
shortest path distance from
time edge
Eifshortest path distance a- n - I
fun i s
removed
and comes back,
s
toa 4by2.
# times one edge can
be removed and =OCn)
come back
# edges
=
=m
# paths
of
O(
)
cost f in
of
BFS
Runtime
Edmonds
- -DinaO(- Karp : mn
m
n
each iteration is ocml
)
Shortest augmenting path: overview of analysis
L1. Throughout the algorithm, length of the shortest path never decreases. L2. After at most m shortest path augmentations, the length of the shortest
augmenting path strictly increases.
Theorem. The shortest augmenting path algorithm runs in O(m2 n) time. Pf.
・O(m + n) time to find shortest augmenting path via BFS. ・O(m) augmentations for paths of length k.
・If there is an augmenting path, there is a simple one.
⇒1≤k
Let 1 ≤ h ≤ n1/2 be layer with min number of nodes: |Vh | ≤ n1/2.
level graph LG for flow f
V0V1 Vh
Vn1/2
86
Unit-capacity simple networks: analysis
L・EMMA 2. After at most n1/2 phases, | f | ≥ | f *| – n1/2.
・After n1/2 phases, length of shortest augmenting path is > n1/2.
・Level graph has more than n1/2 levels.
・Let 1 ≤ h ≤ n1/2 be layer with min number of nodes: |Vh | ≤ n1/2.
・Let A = {v : l(v) < h} ∪ {v : l(v) = h and v has ≤ 1 outgoing residual edge}.
residual graph Gf
A
residual edges
capf(A,B) ≤ |Vh| ≤ n1/2 ⇒ |f| ≥ |f*| – n1/2. ▪
V0V1 Vh
Vn1/2
87