CS计算机代考程序代写 algorithm Network Flow

Network Flow
Ford – Fulkerson algorithm
2021-02-24 CSC373 Winter 2021 – Sam Toueg 1

Example and Main Concepts
2021-02-24 CSC373 Winter 2021 – Sam Toueg 2

Network Flow
Flow Network F = (𝐺,𝑠,𝑡,𝑐) 25
𝑎 15 𝑏
10
𝑡
• 𝐺 = (𝑉, 𝐸): directed graph 𝑠 • 𝑠∈𝑉:noincomingedge
5
𝑐 20
• •
𝑡 ∈ 𝑉: no outgoing edge
𝑐: capacity function 𝐸 → R!”
Ø 𝑐(𝑢, 𝑣) capacity of edge (𝑢, 𝑣) ∈ 𝐸
15
30
𝑑
15 10
2021-02-24 CSC373 Winter 2021 – Sam Toueg
3

Network Flow
Flow Network F = (𝐺, 𝑠, 𝑡, 𝑐)
• 𝐺 = (𝑉, 𝐸): directed graph 𝑠
• 𝑠 ∈ 𝑉: no incoming edge
• 𝑡 ∈ 𝑉: no outgoing edge
• 𝑐: capacity function 𝐸 → R!”
Ø 𝑐(𝑢, 𝑣) capacity of edge (𝑢, 𝑣) ∈ 𝐸 Flow 𝑓: 𝐸 → 𝑅 that respects
Aflow𝑓 withvalue𝑣 𝑓 =20
20/25 𝑎 5/5
0/15
𝑐
15/15 10/15
𝑏 5/10 0/10 𝑡
15/30 15/20 𝑑
1. Capacity constraints: ∀𝑒 ∈ 𝐸: 0 ≤ 𝑓 𝑒 ≤ 𝑐(𝑒)
2. Flowconservation:∀𝑣∈𝑉−{𝑠,𝑡}: ∑#$%&'(𝑓 𝑒 =∑#)*+,*(𝑓 𝑒
Notation
• 𝑓-./𝑣=∑#)*+,$%0(𝑓𝑒
• 𝑓12𝑣=∑#$%&'(𝑓𝑒
• Valueofflow𝑓is𝑣 𝑓 =𝑓-./ 𝑠
2021-02-24 CSC373 Winter 2021 – Sam Toueg 𝑓!” 𝑣 = 𝑓#$% 𝑣 = 13 4

Max Flow Problem
• Problem
ØInput: flow network F = (𝐺, 𝑠, 𝑡, 𝑐) & ØOutput: flow 𝑓 of max value, i.e., ∀ 0low 𝑓 , 𝑣 𝑓
≥ 𝑣(𝑓′)
u
s 30 t
20
10
10
20
2021-02-24
CSC373 Winter 2021 – Sam Toueg
5
v

Max Flow Problem
• Problem
ØInput: flow network F = (𝐺, 𝑠, 𝑡, 𝑐) & ØOutput: flow 𝑓 of max value, i.e., ∀ 0low 𝑓 , 𝑣 𝑓
Suppose we start by sending 20 units of flow along this path
≥ 𝑣(𝑓′)
u
𝟐𝟎/30 t
𝟐𝟎/20
But this is NOT a max flow!
𝟐𝟎/20 s
0/10
0/10
2021-02-24
CSC373 Winter 2021 – Sam Toueg
7
v

Max Flow Problem
• Problem
ØInput: flow network F = (𝐺, 𝑠, 𝑡, 𝑐) &
ØOutput: flow 𝑓 of max value, i.e., ∀ 0low 𝑓 , 𝑣 𝑓 ≥ 𝑣(𝑓′)
Suppose we start by sending A max flow
20 units of flow along this path Note: 10 fewer units of flow on 𝑢 → 𝑣
uu
𝟐𝟎/20 s
0/10
0/10 𝟐𝟎/30
𝟐𝟎/20
t
s
𝟐𝟎/20 𝟏𝟎/10 𝟏𝟎/30
𝟏𝟎/10 𝟐𝟎/20
t
2021-02-24
CSC373 Winter 2021 – Sam Toueg
8
vv

Max Flow Problem
• Problem
ØInput: flow network F = (𝐺, 𝑠, 𝑡, 𝑐) &
ØOutput: flow 𝑓 of max value, i.e., ∀ 0low 𝑓 , 𝑣 𝑓 ≥ 𝑣(𝑓′)
A max flow
Note: 10 fewer units of flow on 𝑢 → 𝑣
uu
𝟐𝟎/20 0/10 s 𝟐𝟎/30
𝟏𝟎/10 𝟐𝟎/20
t
s
𝟐𝟎/20 𝟏𝟎/10 𝟏𝟎/30
𝟏𝟎/10 𝟐𝟎/20
t
vv
2021-02-24 CSC373 Winter 2021 – Sam Toueg
10

Max Flow Problem
• Problem
ØInput: flow network F = (𝐺, 𝑠, 𝑡, 𝑐) &
ØOutput: flow 𝑓 of max value, i.e., ∀ 0low 𝑓 , 𝑣 𝑓 ≥ 𝑣(𝑓′)
We can send a “reverse” flow of 10 A max flow unitsalong𝑣→𝑢! Note: 10fewerunitsofflowon𝑢→𝑣
uu
𝟐𝟎/20 0/10 s 𝟏𝟎𝟐𝟎/30
𝟏𝟎/10 𝟐𝟎/20
t
s
𝟐𝟎/20 𝟏𝟎/10 𝟏𝟎/30
𝟏𝟎/10 𝟐𝟎/20
t
vv
2021-02-24 CSC373 Winter 2021 – Sam Toueg
11

Max Flow Problem
• Problem
ØInput: flow network F = (𝐺, 𝑠, 𝑡, 𝑐) &
ØOutput: flow 𝑓 of max value, i.e., ∀ 0low 𝑓 , 𝑣 𝑓 ≥ 𝑣(𝑓′)
We can send a “reverse” flow of 10 units along 𝑣 → 𝑢 !
So now we get an optimal flow uu
𝟐𝟎/20 𝟏𝟎/10 s 𝟏𝟎𝟐𝟎/30
𝟏𝟎/10 𝟐𝟎/20
t
s
𝟐𝟎/20 𝟏𝟎/10 𝟏𝟎/30
𝟏𝟎/10 𝟐𝟎/20
t
vv
2021-02-24 CSC373 Winter 2021 – Sam Toueg
12

Residual Graph
Residual graph 𝐺, of flow 𝑓:
• 𝐺3 has the same vertices as 𝐺
• Foreachedgee=(𝑢,𝑣)in𝐺,𝐺3 hasatmosttwoedges:
•
1. Forward edge 𝑒 = (𝑢,𝑣) with residual capacity 𝑐 𝑒 − 𝑓 𝑒 > 0 Ø We can send this much additional flow on 𝑒
2. Reverse edge 𝑒4#( = (𝑣, 𝑢) with residual capacity 𝑓(𝑒) > 0
Ø The maximum “reverse” flow that we can send on edge 𝑒; this is the
maximum amount we can reduce the flow on 𝑒, which is 𝑓 𝑒
We added a (forward or reverse) edge to 𝐺3 only if its residual capacity > 0!
u
s 20/30 t
u s𝟐𝟎𝟏𝟎 t
forward
reverse
Flow 𝑓
20/20
Residual graph 𝐺&
𝟐𝟎
𝟏𝟎
0/10
0/10 20/20
𝟏𝟎
𝟐𝟎
2021-02-24
CSC373 Winter 2021 – Sam Toueg
13
v
v

Augmenting Paths
• Let𝑃bean𝑠⤳𝑡pathintheresidualgraph𝐺)
• bottleneck 𝑃, 𝑓 : smallest residual capacity among all edges in 𝑃
• “Augment” flow 𝑓 by “sending” bottleneck 𝑃, 𝑓 units of flow along 𝑃
Ø What does it mean to send 𝑥 > 0 units of flow along 𝑃? For each forward edge 𝑒 ∈ 𝑃, increase the flow on 𝑒 by 𝑥 For each reverse edge 𝑒4#( ∈ 𝑃, decrease the flow on 𝑒 by 𝑥
• Let’s first argue that the new flow 𝑓′ is better than 𝑓
an augmenting path u
augmented flow u
forward
reverse
Flow 𝑓 𝑓′ 20/20
Residual graph 𝐺&
s𝟐𝟎𝟏𝟎 t
10/10
s 10/30 t
𝟐𝟎
𝟏𝟎
𝟏𝟎
𝟐𝟎
10/10 2021-02-24
20/20
v
v
CSC373 Winter 2021 – Sam Toueg
24

Augmenting Paths
• Let𝑃bean𝑠⤳𝑡pathintheresidualgraph𝐺)
• bottleneck 𝑃, 𝑓 : smallest residual capacity among all edges in 𝑃
• “Augment” flow 𝑓 by “sending” bottleneck 𝑃, 𝑓 units of flow along 𝑃
Ø What does it mean to send 𝑥 > 0 units of flow along 𝑃? For each forward edge 𝑒 ∈ 𝑃, increase the flow on 𝑒 by 𝑥 For each reverse edge 𝑒4#( ∈ 𝑃, decrease the flow on 𝑒 by 𝑥
• Let’s first argue that the new flow 𝑓′ is better than 𝑓
Ø Note that the first edge 𝑠, 𝑢 of 𝑃 in 𝐺3 must be a forward edge
(because the original graph 𝐺 has no edge into 𝑠!) ØSo𝑓′(𝑠,𝑢)=𝑓 𝑠,𝑢 +𝑥with𝑥>0
⇒𝑣𝑓5 ≥𝑣𝑓+𝑥
2021-02-24 CSC373 Winter 2021 – Sam Toueg 25

Augmenting Paths
• Let𝑃bean𝑠⤳𝑡pathintheresidualgraph𝐺)
• bottleneck 𝑃, 𝑓 : smallest residual capacity among all edges in 𝑃
• “Augment” flow 𝑓 by “sending” bottleneck 𝑃, 𝑓 units of flow along 𝑃
Ø What does it mean to send 𝑥 > 0 units of flow along 𝑃? For each forward edge 𝑒 ∈ 𝑃, increase the flow on 𝑒 by 𝑥 For each reverse edge 𝑒4#( ∈ 𝑃, decrease the flow on 𝑒 by 𝑥
• Let’s now argue that the new flow 𝑓′ is a valid flow
• (1) Capacity constraints:
Ø If we increased the flow on 𝑒, we did so by at most the residual capacity of forwardedge𝑒in𝐺3,whichis𝑐 𝑒 −𝑓 𝑒
⇒thenewflow𝑓5(𝑒)isatmost𝑓 𝑒 + 𝑐 𝑒 −𝑓 𝑒 =𝑐(𝑒)
Ø If we decreased the flow on 𝑒, we did so by at most the residual capacity of
reverse edge 𝑒4#( in 𝐺3, which is 𝑓 𝑒 ⇒thenewflow𝑓5(𝑒)isatleast𝑓 𝑒 −𝑓 𝑒 =0
2021-02-24 CSC373 Winter 2021 – Sam Toueg 27

Augmenting Paths
• (2) Flow conservation: Augmenting path in residual graph 𝐺&:
svt
FF FR
RF RR
+𝑥 +𝑥
−𝑥 −𝑥
In 𝐺: +𝑥 v
both in and out edges increase by 𝑥
no change
no change
both in and out edges decrease by 𝑥
4 possible cases:
v
v
v
−𝑥 +𝑥 −𝑥
2021-02-24
CSC373 Winter 2021 – Sam Toueg
30

Augmenting Paths
• (2) Flow conservation: Augmenting path in residual graph 𝐺&:
svt
FF FR
RF RR
Flow 𝑓 20/20
Residual graph 𝐺& 0/10 𝟐𝟎
u
𝟏𝟎
F
R
u
s 20/30 t s 𝟐𝟎𝟏𝟎 t
0/10
+𝑥 +𝑥
−𝑥 −𝑥
20/20 𝟏𝟎
𝟐𝟎
v
In 𝐺: +𝑥
v
both in and out edges
increase by 𝑥 no change
no change
both in and out edges decrease by 𝑥
4 possible cases:
v v
v v
−𝑥 +𝑥 −𝑥
2021-02-24
CSC373 Winter 2021 – Sam Toueg
31

The Algorithm
2021-02-24 CSC373 Winter 2021 – Sam Toueg 32

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(𝑢,𝑣)of𝐺do𝑓 𝑢,𝑣 =0 construct 𝐺3
while𝐺3 hasan𝑠⤳𝑡pathdo:
𝑃 ← any simple 𝑠 ⤳ 𝑡 path in 𝐺3 𝑓 ← augment(𝑓, 𝑃)
update 𝐺3
F = (𝐺, 𝑠, 𝑡, 𝑐)
return 𝑓
𝑓𝑎0/15𝑏 𝐺&𝑎15𝑏
0/25 0/10 25
𝑠 0/5 0/15 0/10 𝑡 𝑠 5 15 10
10
𝑡
30
0/15
0/30 15 CSC373 Winter 2021 – Sam Toueg
𝑐 0/20 𝑑
𝑐 20 𝑑
2021-02-24
33

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(𝑢,𝑣)of𝐺do𝑓 𝑢,𝑣 =0 construct 𝐺3
while𝐺3 hasan𝑠⤳𝑡pathdo:
𝑃 ← any simple 𝑠 ⤳ 𝑡 path in 𝐺3 𝑓 ← augment(𝑓, 𝑃)
update 𝐺3
return 𝑓
𝑓𝑎0/15𝑏 𝐺&𝑎15𝑏
0/25 0/10 25
𝑠 0/5 0/15 0/10 𝑡 𝑠 5 15 10
10
𝑡
30
0/15
0/30 15 CSC373 Winter 2021 – Sam Toueg
𝑐 0/20 𝑑
𝑐 20 𝑑
2021-02-24
34

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(𝑢,𝑣)of𝐺do𝑓 𝑢,𝑣 =0 construct 𝐺3
while𝐺3 hasan𝑠⤳𝑡pathdo:
𝑃 ← any simple 𝑠 ⤳ 𝑡 path in 𝐺3 𝑓 ← augment(𝑓, 𝑃)
update 𝐺3
return 𝑓
𝑓𝑎0/15𝑏 𝐺&𝑎15𝑏
10 𝑠 0/5 0/15 0/10 𝑡 𝑠 5 15 10
bottleneck in augmenting path 0/25 0/10 25
0/15
0/30 15 CSC373 Winter 2021 – Sam Toueg
𝑡
30
𝑐 0/20 𝑑
𝑐 20 𝑑
2021-02-24
38

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(𝑢,𝑣)of𝐺do𝑓 𝑢,𝑣 =0 construct 𝐺3
while𝐺3 hasan𝑠⤳𝑡pathdo:
𝑃 ← any simple 𝑠 ⤳ 𝑡 path in 𝐺3 𝑓 ← augment(𝑓, 𝑃)
update 𝐺3
return 𝑓
𝑓𝑎0/15𝑏 𝐺&𝑎15𝑏
5/25 0/10 25
𝑠 0/5 0/15 0/10 𝑡 𝑠 5 15 10
10
𝑡
30
0/15
0/30 15 CSC373 Winter 2021 – Sam Toueg
𝑐 0/20 𝑑 augmenting flow 𝑓
𝑐 20 𝑑
2021-02-24
40

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(𝑢,𝑣)of𝐺do𝑓 𝑢,𝑣 =0 construct 𝐺3
while𝐺3 hasan𝑠⤳𝑡pathdo:
𝑃 ← any simple 𝑠 ⤳ 𝑡 path in 𝐺3 𝑓 ← augment(𝑓, 𝑃)
update 𝐺3
return 𝑓
𝑓𝑎0/15𝑏 𝐺&𝑎15𝑏
5/25 0/10 25
𝑠 5/5 0/15 0/10 𝑡 𝑠 5 15 10
10
𝑡
30
0/15
0/30 15 CSC373 Winter 2021 – Sam Toueg
𝑐 0/20 𝑑 augmenting flow 𝑓
𝑐 20 𝑑
2021-02-24
41

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(𝑢,𝑣)of𝐺do𝑓 𝑢,𝑣 =0 construct 𝐺3
while𝐺3 hasan𝑠⤳𝑡pathdo:
𝑃 ← any simple 𝑠 ⤳ 𝑡 path in 𝐺3 𝑓 ← augment(𝑓, 𝑃)
update 𝐺3
return 𝑓
𝑓𝑎0/15𝑏 𝐺&𝑎15𝑏
5/25 0/10 25
𝑠 5/5 0/15 0/10 𝑡 𝑠 5 15 10
10
𝑡
30
0/15
0/30 15 CSC373 Winter 2021 – Sam Toueg
𝑐 5/20 𝑑 augmenting flow 𝑓
𝑐 20 𝑑
2021-02-24
42

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(𝑢,𝑣)of𝐺do𝑓 𝑢,𝑣 =0 construct 𝐺3
while𝐺3 hasan𝑠⤳𝑡pathdo:
𝑃 ← any simple 𝑠 ⤳ 𝑡 path in 𝐺3 𝑓 ← augment(𝑓, 𝑃)
update 𝐺3
return 𝑓
𝑓𝑎0/15𝑏 𝐺&𝑎15𝑏
5/25 0/10 25
𝑠 5/5 0/15 0/10 𝑡 𝑠 5 15 10
10
𝑡
30
0/15
5/30 15 CSC373 Winter 2021 – Sam Toueg
𝑐 5/20 𝑑 augmented flow
𝑐 20 𝑑
2021-02-24
43

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(𝑢,𝑣)of𝐺do𝑓 𝑢,𝑣 =0 construct 𝐺3
while𝐺3 hasan𝑠⤳𝑡pathdo:
𝑃 ← any simple 𝑠 ⤳ 𝑡 path in 𝐺3 𝑓 ← augment(𝑓, 𝑃)
update 𝐺3
now update 𝐺& 𝑓𝑎0/15𝑏 𝐺&𝑎15𝑏
10 𝑠 5/5 0/15 0/10 𝑡 𝑠 5 15 10
return 𝑓
5/25 0/10 25
0/15
5/30 15 CSC373 Winter 2021 – Sam Toueg
𝑡
30
𝑐 5/20 𝑑 augmented flow
𝑐 20 𝑑
2021-02-24
44

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(𝑢,𝑣)of𝐺do𝑓 𝑢,𝑣 =0 construct 𝐺3
while𝐺3 hasan𝑠⤳𝑡pathdo:
𝑃 ← any simple 𝑠 ⤳ 𝑡 path in 𝐺3 𝑓 ← augment(𝑓, 𝑃)
update 𝐺3
now update 𝐺& 𝑓𝑎0/15𝑏 𝐺&5𝑎15𝑏
return 𝑓
5/25 0/10 20
10 30
45
𝑠 5/5 0/15 0/10 𝑡 𝑠 5 15 10
𝑡
0/15
5/30 15 CSC373 Winter 2021 – Sam Toueg
𝑐 5/20 𝑑 augmented flow
𝑐 20 𝑑
2021-02-24

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(𝑢,𝑣)of𝐺do𝑓 𝑢,𝑣 =0 construct 𝐺3
while𝐺3 hasan𝑠⤳𝑡pathdo:
𝑃 ← any simple 𝑠 ⤳ 𝑡 path in 𝐺3 𝑓 ← augment(𝑓, 𝑃)
update 𝐺3
return 𝑓
𝑓𝑎0/15𝑏 𝐺&5𝑎15𝑏
5/25 0/10 20
𝑠 5/5 0/15 0/10 𝑡 𝑠 5 15 10
10 30
46
𝑡
0/15
5/30 15 CSC373 Winter 2021 – Sam Toueg
𝑐 5/20 𝑑
𝑐 20 𝑑
2021-02-24

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(𝑢,𝑣)of𝐺do𝑓 𝑢,𝑣 =0 construct 𝐺3
while𝐺3 hasan𝑠⤳𝑡pathdo:
𝑃 ← any simple 𝑠 ⤳ 𝑡 path in 𝐺3 𝑓 ← augment(𝑓, 𝑃)
update 𝐺3
return 𝑓
𝑓𝑎0/15𝑏 𝐺&5𝑎15𝑏
5/25 0/10 20
𝑠 5/5 0/15 0/10 𝑡 𝑠 5 15 10
10 30
47
𝑡
0/15
5/30 15 CSC373 Winter 2021 – Sam Toueg
𝑐 5/20 𝑑
𝑐 15 𝑑 5
2021-02-24

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(𝑢,𝑣)of𝐺do𝑓 𝑢,𝑣 =0 construct 𝐺3
while𝐺3 hasan𝑠⤳𝑡pathdo:
𝑃 ← any simple 𝑠 ⤳ 𝑡 path in 𝐺3 𝑓 ← augment(𝑓, 𝑃)
update 𝐺3
return 𝑓
𝑓𝑎0/15𝑏 𝐺&5𝑎15𝑏
5/25 0/10 20
𝑠 5/5 0/15 0/10 𝑡 𝑠 5 15 10
10 25
𝑡
0/15
5/30 15 CSC373 Winter 2021 – Sam Toueg
𝑐 5/20 𝑑
5 5
𝑐 15 𝑑
2021-02-24
48

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(𝑢,𝑣)of𝐺do𝑓 𝑢,𝑣 =0 construct 𝐺3
while𝐺3 hasan𝑠⤳𝑡pathdo:
𝑃 ← any simple 𝑠 ⤳ 𝑡 path in 𝐺3 𝑓 ← augment(𝑓, 𝑃)
update 𝐺3
find another augmentation path in 𝐺& 𝑓𝑎0/15𝑏 𝐺&5𝑎15𝑏
return 𝑓
5/25 0/10 20
10 25
𝑠 5/5 0/15 0/10 𝑡 𝑠 5 15 10
𝑡
0/15
5/30 15 CSC373 Winter 2021 – Sam Toueg
𝑐 5/20 𝑑
5 5
𝑐 15 𝑑
2021-02-24
49

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(𝑢,𝑣)of𝐺do𝑓 𝑢,𝑣 =0 construct 𝐺3
while𝐺3 hasan𝑠⤳𝑡pathdo:
𝑃 ← any simple 𝑠 ⤳ 𝑡 path in 𝐺3 𝑓 ← augment(𝑓, 𝑃)
update 𝐺3
find another augmentation path in 𝐺& 𝑓𝑎0/15𝑏 𝐺&5𝑎15𝑏
return 𝑓
5/25 0/10 20
10 25
𝑠 5/5 0/15 0/10 𝑡 𝑠 5 15 10
𝑡
5
0/15
5/30 15 CSC373 Winter 2021 – Sam Toueg
𝑐 5/20 𝑑
𝑐 15 𝑑 5
2021-02-24
50

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(𝑢,𝑣)of𝐺do𝑓 𝑢,𝑣 =0 construct 𝐺3
while𝐺3 hasan𝑠⤳𝑡pathdo:
𝑃 ← any simple 𝑠 ⤳ 𝑡 path in 𝐺3 𝑓 ← augment(𝑓, 𝑃)
update 𝐺3
return 𝑓
𝑓 𝑎10/15𝑏 𝐺&5𝑎15𝑏
15/25 10/10 20
𝑠 5/5 0/15 0/10 𝑡 𝑠 5 15 10
10 25
𝑡
5
0/15
5/30 15 CSC373 Winter 2021 – Sam Toueg
𝑐 5/20 𝑑 augmented flow
𝑐 15 𝑑 5
2021-02-24
51

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(𝑢,𝑣)of𝐺do𝑓 𝑢,𝑣 =0 construct 𝐺3
while𝐺3 hasan𝑠⤳𝑡pathdo:
𝑃 ← any simple 𝑠 ⤳ 𝑡 path in 𝐺3 𝑓 ← augment(𝑓, 𝑃)
update 𝐺3
return 𝑓
𝑓 𝑎10/15𝑏
now update 𝐺& 𝐺&5𝑎15𝑏
15/25
𝑠 5/5 0/15 0/10 𝑡 𝑠 5 15 10
0/15
10/10 20 5/30 15
10 25
𝑡
5
𝑐 5/20 𝑑 augmented flow
𝑐 15 𝑑 5
2021-02-24
CSC373 Winter 2021 – Sam Toueg
52

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(𝑢,𝑣)of𝐺do𝑓 𝑢,𝑣 =0 construct 𝐺3
while𝐺3 hasan𝑠⤳𝑡pathdo:
𝑃 ← any simple 𝑠 ⤳ 𝑡 path in 𝐺3 𝑓 ← augment(𝑓, 𝑃)
update 𝐺3
return 𝑓
𝑓 𝑎10/15𝑏 𝐺&15𝑎15𝑏
5/30 15 CSC373 Winter 2021 – Sam Toueg
15/25 10/10 10
𝑠 5/5 0/15 0/10 𝑡 𝑠 5 15 10
10 25
𝑡
5
0/15
𝑐 5/20 𝑑
𝑐 15 𝑑 5
2021-02-24
53

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(𝑢,𝑣)of𝐺do𝑓 𝑢,𝑣 =0 construct 𝐺3
while𝐺3 hasan𝑠⤳𝑡pathdo:
𝑃 ← any simple 𝑠 ⤳ 𝑡 path in 𝐺3 𝑓 ← augment(𝑓, 𝑃)
update 𝐺3
return 𝑓
𝑓 𝑎10/15𝑏
10
𝐺&15𝑎5𝑏 10/10 10
15/25
𝑠 5/5 0/15 0/10 𝑡 𝑠 5 15 10
10 25
𝑡
5
0/15
5/30 15 CSC373 Winter 2021 – Sam Toueg
𝑐 5/20 𝑑
𝑐 15 𝑑 5
2021-02-24
54

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(𝑢,𝑣)of𝐺do𝑓 𝑢,𝑣 =0 construct 𝐺3
while𝐺3 hasan𝑠⤳𝑡pathdo:
𝑃 ← any simple 𝑠 ⤳ 𝑡 path in 𝐺3 𝑓 ← augment(𝑓, 𝑃)
update 𝐺3
return 𝑓
𝑓 𝑎10/15𝑏
10 𝐺&15𝑎5𝑏
10 𝑠 5/5 0/15 0/10 𝑡 𝑠 5 15 10
15/25
10/10 10 5/30 15
𝑡
0/15
25
𝑐 5/20 𝑑
5 5
𝑐 15 𝑑
2021-02-24
CSC373 Winter 2021 – Sam Toueg
55

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(𝑢,𝑣)of𝐺do𝑓 𝑢,𝑣 =0 construct 𝐺3
while𝐺3 hasan𝑠⤳𝑡pathdo:
𝑃 ← any simple 𝑠 ⤳ 𝑡 path in 𝐺3 𝑓 ← augment(𝑓, 𝑃)
update 𝐺3
find another augmentation path in 𝐺& 10
return 𝑓
𝑓 𝑎10/15𝑏
𝐺&15𝑎5𝑏 10/10 10
10 𝑠 5/5 0/15 0/10 𝑡 𝑠 5 15 10
15/25
𝑡
0/15
5/30 15 CSC373 Winter 2021 – Sam Toueg
25
𝑐 5/20 𝑑
5 5
𝑐 15 𝑑
2021-02-24
56

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(𝑢,𝑣)of𝐺do𝑓 𝑢,𝑣 =0 construct 𝐺3
while𝐺3 hasan𝑠⤳𝑡pathdo:
𝑃 ← any simple 𝑠 ⤳ 𝑡 path in 𝐺3 𝑓 ← augment(𝑓, 𝑃)
update 𝐺3
find another augmentation path in 𝐺& 10
return 𝑓
𝑓 𝑎10/15𝑏
𝐺&15𝑎5𝑏 10/10 10
10 𝑠 5/5 0/15 0/10 𝑡 𝑠 5 15 10
15/25
𝑡
0/15
5/30 15 CSC373 Winter 2021 – Sam Toueg
25
𝑐 5/20 𝑑
5 5
𝑐 15 𝑑
2021-02-24
57

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(𝑢,𝑣)of𝐺do𝑓 𝑢,𝑣 =0 construct 𝐺3
while𝐺3 hasan𝑠⤳𝑡pathdo:
𝑃 ← any simple 𝑠 ⤳ 𝑡 path in 𝐺3 𝑓 ← augment(𝑓, 𝑃)
update 𝐺3
find another augmentation path in 𝐺& 10
return 𝑓
𝑓 𝑎10/15𝑏
𝐺&15𝑎5𝑏 10/10 10
10
𝑡
25
5
15/25
𝑠 5/5 0/15 0/10 𝑡 𝑠 5 15 10
0/15
5/30 15 CSC373 Winter 2021 – Sam Toueg
𝑐 5/20 𝑑
𝑐 15 𝑑 5
2021-02-24
58

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(𝑢,𝑣)of𝐺do𝑓 𝑢,𝑣 =0 construct 𝐺3
while𝐺3 hasan𝑠⤳𝑡pathdo:
𝑃 ← any simple 𝑠 ⤳ 𝑡 path in 𝐺3 𝑓 ← augment(𝑓, 𝑃)
update 𝐺3
return 𝑓
𝑓 𝑎10/15𝑏
10 𝐺&15𝑎5𝑏
10
𝑡
25
5
15/25
𝑠 5/5 0/15 0/10 𝑡 𝑠 5 15 10
15/15
10/10 10 20/30 15
𝑐 20/20 𝑑 augmented flow
𝑐 15 𝑑 5
2021-02-24
CSC373 Winter 2021 – Sam Toueg
59

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(𝑢,𝑣)of𝐺do𝑓 𝑢,𝑣 =0 construct 𝐺3
while𝐺3 hasan𝑠⤳𝑡pathdo:
𝑃 ← any simple 𝑠 ⤳ 𝑡 path in 𝐺3 𝑓 ← augment(𝑓, 𝑃)
update 𝐺3
now update 𝐺&
10
return 𝑓
𝑓 𝑎10/15𝑏
𝐺&15𝑎5𝑏 10/10 10
10
𝑡
25
5
15/25
𝑠 5/5 0/15 0/10 𝑡 𝑠 5 15 10
15/15
20/30 15 CSC373 Winter 2021 – Sam Toueg
𝑐 20/20 𝑑 augmented flow
𝑐 15 𝑑 5
2021-02-24
60

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(𝑢,𝑣)of𝐺do𝑓 𝑢,𝑣 =0 construct 𝐺3
while𝐺3 hasan𝑠⤳𝑡pathdo:
𝑃 ← any simple 𝑠 ⤳ 𝑡 path in 𝐺3 𝑓 ← augment(𝑓, 𝑃)
update 𝐺3
return 𝑓
10
𝑎5𝑏 5 1510
𝑎 10/15 𝑏
𝑠 5/50/150/10 𝑡 𝑠
𝑓
15/15
𝑐
𝐺& 15 10
10
𝑡
15/25
10/10
20/30
25
15 𝑐 15 𝑑 5
5
20/20
𝑑
2021-02-24
CSC373 Winter 2021 – Sam Toueg
61

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(𝑢,𝑣)of𝐺do𝑓 𝑢,𝑣 =0 construct 𝐺3
while𝐺3 hasan𝑠⤳𝑡pathdo:
𝑃 ← any simple 𝑠 ⤳ 𝑡 path in 𝐺3 𝑓 ← augment(𝑓, 𝑃)
update 𝐺3
return 𝑓
10
𝑎5𝑏 5 1510
𝑎 10/15 𝑏
𝑠 5/50/150/10 𝑡 𝑠
𝑓
15/15
𝑐
𝐺& 15 10
10
𝑡
15/25
10/10
20/30
𝑑 15𝑐𝑑5
20
25
20/20
2021-02-24
CSC373 Winter 2021 – Sam Toueg
62

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(𝑢,𝑣)of𝐺do𝑓 𝑢,𝑣 =0 construct 𝐺3
while𝐺3 hasan𝑠⤳𝑡pathdo:
𝑃 ← any simple 𝑠 ⤳ 𝑡 path in 𝐺3 𝑓 ← augment(𝑓, 𝑃)
update 𝐺3
return 𝑓
10
𝑎5𝑏 5 1510
𝑓
𝐺& 15 10
10
𝑎 10/15 𝑏
𝑠 5/50/150/10 𝑡 𝑠
15/15
𝑐
15/25
10/10
𝑡 𝑑 15𝑐𝑑20
20/30
10
20/20
2021-02-24
CSC373 Winter 2021 – Sam Toueg
63
20

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(𝑢,𝑣)of𝐺do𝑓 𝑢,𝑣 =0 construct 𝐺3
𝑓
𝐺& 15 10
𝑎5𝑏 5 1510
10
while𝐺3 hasan𝑠⤳𝑡pathdo:
𝑃 ← any simple 𝑠 ⤳ 𝑡 path in 𝐺3 𝑓 ← augment(𝑓, 𝑃)
update 𝐺3
return 𝑓
find another augmentation path in 𝐺& 10
𝑎 10/15 𝑏
𝑠 5/50/150/10 𝑡 𝑠
15/15
𝑐
15/25
10/10
𝑡 𝑑 15𝑐𝑑20
20/30
10
20/20
2021-02-24
CSC373 Winter 2021 – Sam Toueg
64
20

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(𝑢,𝑣)of𝐺do𝑓 𝑢,𝑣 =0 construct 𝐺3
while𝐺3 hasan𝑠⤳𝑡pathdo:
𝑃 ← any simple 𝑠 ⤳ 𝑡 path in 𝐺3 𝑓 ← augment(𝑓, 𝑃)
update 𝐺3
return 𝑓
10
𝑎5𝑏 5 1510
𝑓
𝐺& 15 10
10
𝑎 10/15 𝑏
𝑠 5/50/150/10 𝑡 𝑠
15/15
𝑐
15/25
10/10
𝑡 𝑑 15𝑐𝑑20
20/30
10
20/20
2021-02-24
CSC373 Winter 2021 – Sam Toueg
65
20

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(𝑢,𝑣)of𝐺do𝑓 𝑢,𝑣 =0 construct 𝐺3
while𝐺3 hasan𝑠⤳𝑡pathdo:
𝑃 ← any simple 𝑠 ⤳ 𝑡 path in 𝐺3 𝑓 ← augment(𝑓, 𝑃)
update 𝐺3
return 𝑓
10
𝑎5𝑏 5 1510
𝑓
𝐺& 15 10
10
𝑎 15/15 𝑏
𝑠 5/50/155/10 𝑡 𝑠
15/15
𝑐
20/25
10/10
𝑡 𝑑 15𝑐𝑑20
25/30
10
20/20 augmented flow
20
2021-02-24
CSC373 Winter 2021 – Sam Toueg
66

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(𝑢,𝑣)of𝐺do𝑓 𝑢,𝑣 =0 construct 𝐺3
𝑓
𝐺& 15 10
𝑎5𝑏 5 1510
10
while𝐺3 hasan𝑠⤳𝑡pathdo:
𝑃 ← any simple 𝑠 ⤳ 𝑡 path in 𝐺3 𝑓 ← augment(𝑓, 𝑃)
update 𝐺3
return 𝑓
now update 𝐺&
10
𝑎 15/15 𝑏
𝑠 5/50/155/10 𝑡 𝑠
15/15
𝑐
20/25
10/10
𝑡 𝑑 15𝑐𝑑20
25/30
10
20/20 augmented flow
20
2021-02-24
CSC373 Winter 2021 – Sam Toueg
67

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(𝑢,𝑣)of𝐺do𝑓 𝑢,𝑣 =0 construct 𝐺3
while𝐺3 hasan𝑠⤳𝑡pathdo:
𝑃 ← any simple 𝑠 ⤳ 𝑡 path in 𝐺3 𝑓 ← augment(𝑓, 𝑃)
update 𝐺3
return 𝑓
10
𝑎5𝑏 5 1510
𝑓
𝐺& 20 5
10
𝑎 15/15 𝑏
𝑠 5/50/155/10 𝑡 𝑠
15/15
𝑐
20/25
10/10
𝑡 𝑑 15𝑐𝑑20
25/30
10
20/20
2021-02-24
CSC373 Winter 2021 – Sam Toueg
68
20

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(𝑢,𝑣)of𝐺do𝑓 𝑢,𝑣 =0 construct 𝐺3
while𝐺3 hasan𝑠⤳𝑡pathdo:
𝑃 ← any simple 𝑠 ⤳ 𝑡 path in 𝐺3 𝑓 ← augment(𝑓, 𝑃)
update 𝐺3
return 𝑓
𝑓
𝐺& 20 5
𝑎𝑏
𝑎 15/15 𝑏
𝑠 5/50/155/10 𝑡 𝑠
15
𝑡 𝑑 15𝑐𝑑20
20
20/25
10/10
10 5 1510
15/15
𝑐
25/30
10
20/20
2021-02-24
CSC373 Winter 2021 – Sam Toueg
69

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(𝑢,𝑣)of𝐺do𝑓 𝑢,𝑣 =0 construct 𝐺3
while𝐺3 hasan𝑠⤳𝑡pathdo:
𝑃 ← any simple 𝑠 ⤳ 𝑡 path in 𝐺3 𝑓 ← augment(𝑓, 𝑃)
update 𝐺3
return 𝑓
𝑓
𝐺& 20 5
𝑎𝑏
𝑎 15/15 𝑏
𝑠 5/50/155/10 𝑡 𝑠
15
𝑡 𝑑 15𝑐𝑑20
20
20/25
10/10
10 5 15 5
5
15/15
𝑐
25/30
10
20/20
2021-02-24
CSC373 Winter 2021 – Sam Toueg
70

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(𝑢,𝑣)of𝐺do𝑓 𝑢,𝑣 =0 construct 𝐺3
while𝐺3 hasan𝑠⤳𝑡pathdo:
𝑃 ← any simple 𝑠 ⤳ 𝑡 path in 𝐺3 𝑓 ← augment(𝑓, 𝑃)
update 𝐺3
return 𝑓
𝑓
𝐺& 20 5
𝑎𝑏
𝑎 15/15 𝑏
𝑠 5/50/155/10 𝑡 𝑠
15
𝑡 𝑑 15𝑐𝑑25
20
20/25
10/10
10 5 15 5
5
15/15
𝑐
25/30
5
20/20
2021-02-24
CSC373 Winter 2021 – Sam Toueg
71

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(𝑢,𝑣)of𝐺do𝑓 𝑢,𝑣 =0 construct 𝐺3
𝑓
𝐺& 20 5
𝑎𝑏
while𝐺3 hasan𝑠⤳𝑡pathdo:
𝑃 ← any simple 𝑠 ⤳ 𝑡 path in 𝐺3 𝑓 ← augment(𝑓, 𝑃)
update 𝐺3
return 𝑓
find another augmentation path in 𝐺& 15
𝑎 15/15 𝑏
𝑠 5/50/155/10 𝑡 𝑠
20/25
10/10
10 5 15 5
𝑡 𝑑 15𝑐𝑑25
20
5
15/15
𝑐
25/30
5
20/20
2021-02-24
CSC373 Winter 2021 – Sam Toueg
72

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(𝑢,𝑣)of𝐺do𝑓 𝑢,𝑣 =0 construct 𝐺3
while𝐺3 hasan𝑠⤳𝑡pathdo:
𝑃 ← any simple 𝑠 ⤳ 𝑡 path in 𝐺3 𝑓 ← augment(𝑓, 𝑃)
update 𝐺3
return𝑓 𝑣 𝑓 =20+15=35
there is no 𝑠 ⤳ 𝑡 path in 𝐺& Finito! Return 𝑓
15
𝑡 𝑑 15𝑐𝑑25
20
𝑓
𝐺& 20 5
𝑎𝑏
𝑎 15/15 𝑏
𝑠 5/50/155/10 𝑡 𝑠
20/25
10/10
10 5 15 5
5
15/15
𝑐
25/30
5
20/20
2021-02-24
CSC373 Winter 2021 – Sam Toueg
73

Ford-Fulkerson Algorithm
Ford-Fulkerson(F): foreachedge(𝑢,𝑣)of𝐺do𝑓 𝑢,𝑣 =0 construct 𝐺3
while𝐺3 hasan𝑠⤳𝑡pathdo:
𝑃 ← any simple 𝑠 ⤳ 𝑡 path in 𝐺3
𝑓 ← augment(𝑓, 𝑃)
update 𝐺3 return 𝑓
nodes reachable from 𝑠: 𝐴 = {𝑠, 𝑎}
not reachable from 𝑠: 𝐵 = {𝑏, 𝑐, 𝑑, 𝑡}
15 𝑠−𝑡 cut (𝐴, 𝐵)
𝑡 𝑑 15𝑐𝑑25
20
𝑓
𝐺& 20 5
𝑎𝑏
𝑎 15/15 𝑏
𝑠 5/50/155/10 𝑡 𝑠
20/25
10/10
10 5 15 5
5
15/15
𝑐
25/30
5
20/20
2021-02-24
CSC373 Winter 2021 – Sam Toueg
74

Complexity of F-F
2021-02-24 CSC373 Winter 2021 – Sam Toueg 75

Ford-Fulkerson Algorithm Ford-Fulkerson(F): F = (𝐺, 𝑠, 𝑡, 𝑐)
foreachedge(𝑢,𝑣)of𝐺do𝑓 𝑢,𝑣 =0 construct 𝐺3 𝑂(𝑚 + 𝑛)
while𝐺3 hasan𝑠⤳𝑡pathdo:
𝑃 ← any simple 𝑠 ⤳ 𝑡 path in 𝐺3
𝑓 ← augment(𝑓, 𝑃) 𝑂(𝑛) (the length of 𝑃) update 𝐺3 𝑂(𝑛)
return 𝑓
Run time of one iteration of the while loop:
How many iterations?
𝑉 = 𝑛, 𝐸 = 𝑚
𝑂(𝑚 + 𝑛) by BFS or DFS
𝑂 𝑚+𝑛
2021-02-24 CSC373 Winter 2021 – Sam Toueg
76

Ford-Fulkerson Algorithm
Assume: edge capacities are integers
Observations:
1. At every step, flows and residual capacities remain integers 2. Every iteration increases the value of the flow by at least 1 3. 𝑣 max0low ≤𝐶=∑RSRTUVWXY𝑐 𝑒
⇒ after at most 𝐶 iterations, FF algorithm terminates
Run time of one iteration of the while loop:
Total running time:
𝑂(𝑚+𝑛 D𝐶) 𝑂(𝑚 D 𝐶)
𝑂 𝑚+𝑛
assuming all nodes are reachablefrom𝑠,𝑠𝑜𝑚≥𝑛 −1
2021-02-24 CSC373 Winter 2021 – Sam Toueg
77

Termination of Ford-Fulkerson Algorithm
• TotalRunningtime:𝑂( 𝑚+𝑛 ⋅𝐶)
Ø This is pseudo-polynomial time
Ø 𝐶 can be exponentially large in the input length (the number of bits
required to write down the edge capacities)
In the graph below, if we choose augmentation paths arbitrarily
we might end up repeatedly sending 1 unit of flow across 𝑎 → 𝑏 and then reversing it which can be exponential in the length of 𝐶 (in the example 𝐶 = 2000)
𝑎 1𝑡
1000
𝑠
1000
1000
𝑏
1000
2021-02-24
CSC373 Winter 2021 – Sam Toueg 80

Termination of Ford-Fulkerson Algorithm
• TotalRunningtime:𝑂( 𝑚+𝑛 ⋅𝐶)
Ø This is pseudo-polynomial time
Ø 𝐶 can be exponentially large in the input length (the number of bits
required to write down the edge capacities)
In the graph below, if we choose augmentation paths arbitrarily
we might end up repeatedly sending 1 unit of flow across 𝑎 → 𝑏 and then reversing it which can be exponential in the length of 𝐶 (in the example 𝐶 = 2000)
0/1000 𝑎 0/1000 1000 𝑎 1000 𝑓:𝑠 0/1 𝑡 𝐺&:𝑠 1 𝑡
0/1000 0/1000 1000 1000 𝑏𝑏
2021-02-24
CSC373 Winter 2021 – Sam Toueg
81

Termination of Ford-Fulkerson Algorithm
• TotalRunningtime:𝑂( 𝑚+𝑛 ⋅𝐶)
Ø This is pseudo-polynomial time
Ø 𝐶 can be exponentially large in the input length (the number of bits
required to write down the edge capacities)
In the graph below, if we choose augmentation paths arbitrarily
we might end up repeatedly sending 1 unit of flow across 𝑎 → 𝑏 and then reversing it which can be exponential in the length of 𝐶 (in the example 𝐶 = 2000)
0/1000 𝑎 0/1000 1000 𝑎 1000 𝑓:𝑠 0/1 𝑡 𝐺&:𝑠 1 𝑡
0/1000 0/1000 1000 1000 𝑏𝑏
2021-02-24
CSC373 Winter 2021 – Sam Toueg
82

Termination of Ford-Fulkerson Algorithm
• TotalRunningtime:𝑂( 𝑚+𝑛 ⋅𝐶)
Ø This is pseudo-polynomial time
Ø 𝐶 can be exponentially large in the input length (the number of bits
required to write down the edge capacities)
In the graph below, if we choose augmentation paths arbitrarily
we might end up repeatedly sending 1 unit of flow across 𝑎 → 𝑏 and then reversing it which can be exponential in the length of 𝐶 (in the example 𝐶 = 2000)
1/1000 𝑎 0/1000 1000 𝑎 1000 𝑓:𝑠 1/1 𝑡 𝐺&:𝑠 1 𝑡
0/1000 1/1000 1000 1000 𝑏𝑏
2021-02-24
CSC373 Winter 2021 – Sam Toueg
83

Termination of Ford-Fulkerson Algorithm
• TotalRunningtime:𝑂( 𝑚+𝑛 ⋅𝐶)
Ø This is pseudo-polynomial time
Ø 𝐶 can be exponentially large in the input length (the number of bits
required to write down the edge capacities)
In the graph below, if we choose augmentation paths arbitrarily
we might end up repeatedly sending 1 unit of flow across 𝑎 → 𝑏 and then reversing it which can be exponential in the length of 𝐶 (in the example 𝐶 = 2000)
1/1000 𝑎 0/1000 1 𝑎 1000 𝑓:𝑠 𝑡𝐺:𝑠999
1/1 & 1 𝑡 0/1000 1/1000 1000 1000
𝑏𝑏
2021-02-24
CSC373 Winter 2021 – Sam Toueg
84

Termination of Ford-Fulkerson Algorithm
• TotalRunningtime:𝑂( 𝑚+𝑛 ⋅𝐶)
Ø This is pseudo-polynomial time
Ø 𝐶 can be exponentially large in the input length (the number of bits
required to write down the edge capacities)
In the graph below, if we choose augmentation paths arbitrarily
we might end up repeatedly sending 1 unit of flow across 𝑎 → 𝑏 and then reversing it which can be exponential in the length of 𝐶 (in the example 𝐶 = 2000)
1/1000 𝑎 0/1000 1 𝑎 1000 𝑓:𝑠 𝑡𝐺:𝑠999
1/1 & 1 𝑡 0/1000 1/1000 1000 1000
𝑏𝑏
2021-02-24
CSC373 Winter 2021 – Sam Toueg
85

Termination of Ford-Fulkerson Algorithm
• TotalRunningtime:𝑂( 𝑚+𝑛 ⋅𝐶)
Ø This is pseudo-polynomial time
Ø 𝐶 can be exponentially large in the input length (the number of bits
required to write down the edge capacities)
In the graph below, if we choose augmentation paths arbitrarily
we might end up repeatedly sending 1 unit of flow across 𝑎 → 𝑏 and then reversing it which can be exponential in the length of 𝐶 (in the example 𝐶 = 2000)
1/1000 𝑎 0/1000 1 𝑎 1000 𝑓:𝑠 𝑡𝐺:𝑠999
1/1 & 1 𝑡
999
1
0/1000
1/1000 1000 𝑏𝑏
2021-02-24
CSC373 Winter 2021 – Sam Toueg
86

Termination of Ford-Fulkerson Algorithm
• TotalRunningtime:𝑂( 𝑚+𝑛 ⋅𝐶)
Ø This is pseudo-polynomial time
Ø 𝐶 can be exponentially large in the input length (the number of bits
required to write down the edge capacities)
In the graph below, if we choose augmentation paths arbitrarily
we might end up repeatedly sending 1 unit of flow across 𝑎 → 𝑏 and then reversing it which can be exponential in the length of 𝐶 (in the example 𝐶 = 2000)
1/1000 𝑎 0/1000 1 𝑎 1000 𝑓:𝑠 𝑡𝐺:𝑠999
1/1 & 1 𝑡
999
1
0/1000
1/1000 1000 𝑏𝑏
2021-02-24
CSC373 Winter 2021 – Sam Toueg
87

Termination of Ford-Fulkerson Algorithm
• TotalRunningtime:𝑂( 𝑚+𝑛 ⋅𝐶)
Ø This is pseudo-polynomial time
Ø 𝐶 can be exponentially large in the input length (the number of bits
required to write down the edge capacities)
In the graph below, if we choose augmentation paths arbitrarily
we might end up repeatedly sending 1 unit of flow across 𝑎 → 𝑏 and then reversing it which can be exponential in the length of 𝐶 (in the example 𝐶 = 2000)
1/1000 𝑎 1/1000 1 𝑎 1000 𝑓:𝑠 𝑡𝐺:𝑠999
0/1 & 1 𝑡
999
1
1/1000
1/1000 1000 𝑏𝑏
2021-02-24
CSC373 Winter 2021 – Sam Toueg
88

Termination of Ford-Fulkerson Algorithm
• TotalRunningtime:𝑂( 𝑚+𝑛 ⋅𝐶)
Ø This is pseudo-polynomial time
Ø 𝐶 can be exponentially large in the input length (the number of bits
required to write down the edge capacities)
In the graph below, if we choose augmentation paths arbitrarily
we might end up repeatedly sending 1 unit of flow across 𝑎 → 𝑏 and then reversing it which can be exponential in the length of 𝐶 (in the example 𝐶 = 2000)
1/1000 𝑎 1/1000 1 𝑎 1000 𝑓:𝑠 𝑡𝐺:𝑠999
0/1 & 1 𝑡
999
999
1
1/1000 𝑏
1/1000 1 CSC373 Winter 2021 – Sam Toueg
𝑏
2021-02-24
89

Termination of Ford-Fulkerson Algorithm
• TotalRunningtime:𝑂( 𝑚+𝑛 ⋅𝐶)
Ø This is pseudo-polynomial time
Ø 𝐶 can be exponentially large in the input length (the number of bits
required to write down the edge capacities)
In the graph below, if we choose augmentation paths arbitrarily
we might end up repeatedly sending 1 unit of flow across 𝑎 → 𝑏 and then reversing it which can be exponential in the length of 𝐶 (in the example 𝐶 = 2000)
1/1000 𝑎 1/1000 1 𝑎 1000 𝑓:𝑠 𝑡𝐺:𝑠999
0/1 & 1 𝑡
999
999
1
1/1000 𝑏
1/1000 1 CSC373 Winter 2021 – Sam Toueg
𝑏
2021-02-24
90

Termination of Ford-Fulkerson Algorithm
• TotalRunningtime:𝑂( 𝑚+𝑛 ⋅𝐶)
Ø This is pseudo-polynomial time
Ø 𝐶 can be exponentially large in the input length (the number of bits
required to write down the edge capacities)
In the graph below, if we choose augmentation paths arbitrarily
we might end up repeatedly sending 1 unit of flow across 𝑎 → 𝑏 and then reversing it which can be exponential in the length of 𝐶 (in the example 𝐶 = 2000)
1/1000 𝑎 1/1000 1 𝑎 1 𝑓:𝑠 𝑡𝐺:𝑠999999
0/1 & 1 𝑡
999
999
1
1/1000 𝑏
1/1000 1 CSC373 Winter 2021 – Sam Toueg
𝑏
2021-02-24
91

Termination of Ford-Fulkerson Algorithm
• TotalRunningtime:𝑂( 𝑚+𝑛 ⋅𝐶)
Ø This is pseudo-polynomial time
Ø 𝐶 can be exponentially large in the input length (the number of bits
required to write down the edge capacities)
In the graph below, if we choose augmentation paths arbitrarily
we might end up repeatedly sending 1 unit of flow across 𝑎 → 𝑏 and then reversing it which can be exponential in the length of 𝐶 (in the example 𝐶 = 2000)
1/1000 𝑎 1/1000 1 𝑎 1 𝑓:𝑠 𝑡𝐺:𝑠999999
0/1 & 1 𝑡
999
999
1
1/1000 𝑏
1/1000 1 CSC373 Winter 2021 – Sam Toueg
𝑏
2021-02-24
92

Termination of Ford-Fulkerson Algorithm
• TotalRunningtime:𝑂( 𝑚+𝑛 ⋅𝐶)
Ø This is pseudo-polynomial time
Ø 𝐶 can be exponentially large in the input length (the number of bits
required to write down the edge capacities)
In the graph below, if we choose augmentation paths arbitrarily
we might end up repeatedly sending 1 unit of flow across 𝑎 → 𝑏 and then reversing it which can be exponential in the length of 𝐶 (in the example 𝐶 = 2000)
2/1000 𝑎 1/1000 1 𝑎 1 𝑓:𝑠 𝑡𝐺:𝑠999999
1/1 & 1 𝑡
999
999
1
1/1000 𝑏
2/1000 1 CSC373 Winter 2021 – Sam Toueg
𝑏
2021-02-24
93

Termination of Ford-Fulkerson Algorithm
• TotalRunningtime:𝑂( 𝑚+𝑛 ⋅𝐶)
Ø This is pseudo-polynomial time
Ø 𝐶 can be exponentially large in the input length (the number of bits
required to write down the edge capacities)
In the graph below, if we choose augmentation paths arbitrarily
we might end up repeatedly sending 1 unit of flow across 𝑎 → 𝑏 and then reversing it which can be exponential in the length of 𝐶 (in the example 𝐶 = 2000)
2/1000 𝑎 1/1000 2 𝑎 1 𝑓:𝑠 𝑡𝐺:𝑠998999
1/1 & 1 𝑡
999
998
2
1/1000 𝑏
2/1000 1 CSC373 Winter 2021 – Sam Toueg
𝑏
2021-02-24
94

Termination of Ford-Fulkerson Algorithm
• TotalRunningtime:𝑂( 𝑚+𝑛 ⋅𝐶)
Ø This is pseudo-polynomial time
Ø 𝐶 can be exponentially large in the input length (the number of bits
required to write down the edge capacities)
In the graph below, if we choose augmentation paths arbitrarily
we might end up repeatedly sending 1 unit of flow across 𝑎 → 𝑏 and then reversing it which can be exponential in the length of 𝐶 (in the example 𝐶 = 2000)
2/1000 𝑎 1/1000 2 𝑎 1 𝑓:𝑠 𝑡𝐺:𝑠998999
1/1 & 1 𝑡
999
998
2
1/1000 𝑏
2/1000 1 CSC373 Winter 2021 – Sam Toueg
𝑏
2021-02-24
95

Termination of Ford-Fulkerson Algorithm
• TotalRunningtime:𝑂( 𝑚+𝑛 ⋅𝐶)
Ø This is pseudo-polynomial time
Ø 𝐶 can be exponentially large in the input length (the number of bits
required to write down the edge capacities)
In the graph below, if we choose augmentation paths arbitrarily
we might end up repeatedly sending 1 unit of flow across 𝑎 → 𝑏 and then reversing it which can be exponential in the length of 𝐶 (in the example 𝐶 = 2000)
2/1000 𝑎 2/1000 2 𝑎 1 𝑓:𝑠 𝑡𝐺:𝑠998999
0/1 & 1 𝑡
999
998
2
2/1000 𝑏
2/1000 1 CSC373 Winter 2021 – Sam Toueg
𝑏
2021-02-24
96

Termination of Ford-Fulkerson Algorithm
• TotalRunningtime:𝑂( 𝑚+𝑛 ⋅𝐶)
Ø This is pseudo-polynomial time
Ø 𝐶 can be exponentially large in the input length (the number of bits
required to write down the edge capacities)
In the graph below, if we choose augmentation paths arbitrarily
we might end up repeatedly sending 1 unit of flow across 𝑎 → 𝑏 and then reversing it which can be exponential in the length of 𝐶 (in the example 𝐶 = 2000)
2/1000 𝑎 2/1000 2 𝑎 2 𝑓:𝑠 𝑡𝐺:𝑠998998
0/1 & 1 𝑡
998
998
2
2/1000 𝑏
2/1000 2 CSC373 Winter 2021 – Sam Toueg
𝑏
2021-02-24
97

Termination of Ford-Fulkerson Algorithm
• TotalRunningtime:𝑂( 𝑚+𝑛 ⋅𝐶)
Ø This is pseudo-polynomial time
Ø 𝐶 can be exponentially large in the input length (the number of bits required to write down the edge capacities)pacities.
• Can we improve F-F to run in polynomial time?
Yes! by picking augmented path cleverly:
Ø Pick the augmenting path with the maximum bottleneck capacity
• using modified Dijkstra’s algorithm, 𝑂 𝑚 log 𝑛 time for each iteration
• 𝑂 𝑚 log 𝐶 iterations
• total running time 𝑂 𝑚’ log 𝑛 log 𝐶
Ø Pick the shortest augmenting path, i.e., one with the fewest edges
• using BFS, 𝑂 𝑚 time for each iteration
• 𝑂 𝑚𝑛 iterations
• total running time 𝑂 𝑚’𝑛 Edmonds-Karp algorithm
• Other algorithms:
• Dinic’s algorithm 𝑂 𝑚𝑛’ [1970]
• Sleator–Tarjan algorithm 𝑂(𝑚𝑛 log 𝑛) [1983]
• Several other, including…
99

Max Flows in O(nm) Time, or Better
James B. Orlin
Sloan School of Management and Operations Research Center Massachusetts Institute of Technology, Cambridge, MA 02139
jorlin@mit.edu
ABSTRACT
In this paper, we present improved polynomial time algo- rithms for the max flow problem defined on sparse networks with n nodes and m arcs. We show how to solve the max flow problem in time. In the case that m = O(n1.06), this improves upon the best previous al- gorithm due to King, Rao, and Tarjan, who solved the max flow problem in time. This establishes that the max flow problem is solvable in O(nm) time for all values of n and m. In the case that m = O(n), we improve the running time to O(n2/ log n).
Categories and Subject Descriptors
F.2 [Theory of Computation]: Analysis of Algorithms and Problem Complexity
is bounded by U. The fastest strongly polynomial time algorithm is due to King et al. [9]. Its running time is O(nm logm/(n logn) n). When m = Ω(n1+ε ) for any posi- tive constant ε, the running time is O(nm). When m = O(n log n), the running time is O(nm log n). The fastest weakly polynomial time algorithm is due to Goldberg and Rao [7]. Their algorithm solves the max flow problem as a sequence of O(log U ) scaling phases, each of which trans- forms a ∆-optimal flow into a ∆/2-optimal flow. The run- ning time per scaling phase is O(Λm log(n2/m)), where Λ = m i n { n 2/ 3 , m 1 / 2} .
Our contribution.
We show that the max flow problem can be solved in O(nm + m31/16log2n) time. When m = O(n(16/15)−ε ), this running time is O(nm). Because the algorithm by King et al. [9] solves the max flow problem in O(nm) time for m > n1+ε , our improvement establishes that the max flow
STOC’ 2013
General Terms
CSC373 Winter 2021pr-oSbalmemTocuaeng be solved in O(nm) time for all n an1d00m. We also develop an O(n2/ log n) algorithm for max flow prob-
2021-02-24
Algorithms, Theory
O(nm + m31/16log2n)
O(nm logm/(n logn) n)
lems in which m = O(n).

Correctness of F-F
2021-02-24 CSC373 Winter 2021 – Sam Toueg 101

Cuts and Cut Capacities
• Given a flow network F = (𝐺,𝑠,𝑡,𝑐)
• (𝐴,𝐵) is an 𝑠-𝑡 cut of F if (𝐴,𝐵) is a partition of the vertices of 𝐺 with 𝑠 ∈ 𝐴, and 𝑡 ∈ 𝐵
• Capacity of cut 𝐴, 𝐵 : sum of capacities of all edges leaving 𝐴
• That is: 𝑐𝑎𝑝 𝐴, 𝐵 = ∑]∈_,U∈` 𝑐(𝑢, 𝑣)
𝐴 𝑠6𝑡
𝑐𝑎𝑝 𝐴,𝐵 =5+6=11
5
𝐵 = 𝑉\A
2021-02-24
CSC373 Winter 2021 – Sam Toueg 103

Cuts and Flows
Lemma 2: For any flow 𝑓 and any 𝑠-𝑡 cut (𝐴, 𝐵),
𝑣𝑓 =𝑓c]d 𝐴 −𝑓VW(𝐴) where 𝑓c]d 𝐴 =flowfrom𝐴to𝐵=∑R:_→`𝑓 𝑒
𝑓VW 𝐴 =flowfrom𝐵to𝐴=∑R:`→_𝑓 𝑒 Proof: Just need to apply flow conservation (exercise!)
𝑓#$% 𝐴 =5+1=6 𝑓!” 𝐴 =3+2=5
3/10 5/5
𝐴
𝑠 1/6 𝑡
2/3
𝑣 𝑓 =𝑓#$% 𝐴 −𝑓!” 𝐴 =6−5=1
CSC373 Winter 2021 – Sam Toueg 105
𝐵 = 𝑉\A
2021-02-24

Cuts and Flows
Lemma 2: For any flow 𝑓 and any 𝑠-𝑡 cut (𝐴, 𝐵),
𝑣 𝑓 =𝑓c]d 𝐴 −𝑓VW(𝐴)where 𝑓c]d 𝐴 =∑R:_→`𝑓 𝑒 𝑓VW 𝐴 =∑R:`→_𝑓 𝑒
Proof:
𝑣 𝑓 =∑()*+,-./0𝑓 𝑒
=∑$∈2[∑()*+,-./$𝑓𝑒 −∑(*.3*4-./$𝑓𝑒] =∑$∈2∑()*+,-./$𝑓 𝑒 −∑$∈2∑(*.3*4-./$𝑓 𝑒
=∑()*+,-./2𝑓 𝑒 −∑(*.3*4-./2𝑓 𝑒 = ∑(:2→7𝑓 𝑒 +∑(:2→2𝑓 𝑒 −
[∑(:7→2𝑓 𝑒 +∑(:2→2𝑓 𝑒 ] =∑(:2→7𝑓 𝑒 −∑(:7→2𝑓 𝑒 ∎
𝑣𝑓=5+1−3+2 =1
3/10
𝐴 5/5 𝐵=𝑉\A
𝑠 1/6 𝑡 2/3
2021-02-24 CSC373 Winter 2021 – Sam Toueg
106

•
•
Cuts and Flows
Consider any flow network F = (𝐺, 𝑠, 𝑡, 𝑐)
Lemma 3: For any flow 𝑓 and any 𝑠−𝑡 cut (𝐴,𝐵), 𝑣 𝑓
≤ 𝑐𝑎𝑝(𝐴,𝐵)
Proof:
𝑣 𝑓 =𝑓c]d 𝐴 −𝑓VW 𝐴 ≤𝑓c]d 𝐴
= ∑R:_→` 𝑓 𝑒
≤ ∑R:_→` 𝑐 𝑒 =𝑐𝑎𝑝(𝐴,𝐵) ∎
2021-02-24
CSC373 Winter 2021 – Sam Toueg
107

•
• •
Cuts and Flows
Consider any flow network F = (𝐺, 𝑠, 𝑡, 𝑐)
Lemma 3: For any flow 𝑓 and any 𝑠−𝑡 cut (𝐴,𝐵), 𝑣 𝑓 ≤ 𝑐𝑎𝑝(𝐴,𝐵) Corollary 4:
Foranyflow𝑓andany𝑠−𝑡cut 𝐴,𝐵 ,if𝑣 𝑓 =𝑐𝑎𝑝(𝐴,𝐵),then
1) 𝑓 is a max flow, and 2) 𝐴,𝐵 isamincut
A cut with minimum capacity among all 𝑠−𝑡 cuts
Proof:
Let 𝑓∗ be a max flow, and 𝐴∗,𝐵∗ be a min cut
Let 𝑓 be any flow, and 𝐴,𝐵 be any 𝑠−𝑡 cut
𝑣 𝑓 ≤𝑣 𝑓∗ ≤𝑐𝑎𝑝 𝐴∗,𝐵∗ ≤𝑐𝑎𝑝 𝐴,𝐵
Bcs: 𝑓∗ is a max flow
2021-02-24 CSC373 Winter 2021 – Sam Toueg 108

•
• •
Cuts and Flows
Consider any flow network F = (𝐺, 𝑠, 𝑡, 𝑐)
Lemma 3: For any flow 𝑓 and any 𝑠−𝑡 cut (𝐴,𝐵), 𝑣 𝑓 ≤ 𝑐𝑎𝑝(𝐴,𝐵) Corollary 4:
Foranyflow𝑓andany𝑠−𝑡cut 𝐴,𝐵 ,if𝑣 𝑓 =𝑐𝑎𝑝(𝐴,𝐵),then
1) 𝑓 is a max flow, and 2) 𝐴,𝐵 isamincut
Proof:
Let 𝑓∗ be a max flow, and 𝐴∗,𝐵∗ be a min cut
Let 𝑓 be any flow, and 𝐴,𝐵 be any 𝑠−𝑡 cut
𝑣 𝑓 ≤𝑣 𝑓∗ ≤𝑐𝑎𝑝 𝐴∗,𝐵∗ ≤𝑐𝑎𝑝 𝐴,𝐵
2021-02-24 CSC373 Winter 2021 – Sam Toueg 109

•
• •
Cuts and Flows
Consider any flow network F = (𝐺, 𝑠, 𝑡, 𝑐)
Lemma 3: For any flow 𝑓 and any 𝑠−𝑡 cut (𝐴,𝐵), 𝑣 𝑓 ≤ 𝑐𝑎𝑝(𝐴,𝐵) Corollary 4:
Foranyflow𝑓andany𝑠−𝑡cut 𝐴,𝐵 ,if𝑣 𝑓 =𝑐𝑎𝑝(𝐴,𝐵),then
1) 𝑓 is a max flow, and 2) 𝐴,𝐵 isamincut
Proof:
Let 𝑓∗ be a max flow, and 𝐴∗,𝐵∗ be a min cut
Let 𝑓 be any flow, and 𝐴,𝐵 be any 𝑠−𝑡 cut
𝑣 𝑓 ≤𝑣 𝑓∗ ≤𝑐𝑎𝑝 𝐴∗,𝐵∗ ≤𝑐𝑎𝑝 𝐴,𝐵
Bcs: 𝐴∗, 𝐵∗ is a min cut 2021-02-24 CSC373 Winter 2021 – Sam Toueg
110

•
• •
Cuts and Flows
Consider any flow network F = (𝐺, 𝑠, 𝑡, 𝑐)
Lemma 3: For any flow 𝑓 and any 𝑠−𝑡 cut (𝐴,𝐵), 𝑣 𝑓 ≤ 𝑐𝑎𝑝(𝐴,𝐵) Corollary 4:
Foranyflow𝑓andany𝑠−𝑡cut 𝐴,𝐵 ,if𝑣 𝑓 =𝑐𝑎𝑝(𝐴,𝐵),then
1) 𝑓 is a max flow, and 2) 𝐴,𝐵 isamincut
Proof:
Let 𝑓∗ be a max flow, and 𝐴∗,𝐵∗ be a min cut
Let 𝑓 be any flow, and 𝐴,𝐵 be any 𝑠−𝑡 cut
𝑣 𝑓 ≤𝑣 𝑓∗ ≤𝑐𝑎𝑝 𝐴∗,𝐵∗ ≤𝑐𝑎𝑝 𝐴,𝐵
By Lemma 3
2021-02-24 CSC373 Winter 2021 – Sam Toueg 111

•
• •
Cuts and Flows
Consider any flow network F = (𝐺, 𝑠, 𝑡, 𝑐)
Lemma 3: For any flow 𝑓 and any 𝑠−𝑡 cut (𝐴,𝐵), 𝑣 𝑓 ≤ 𝑐𝑎𝑝(𝐴,𝐵) Corollary 4:
Foranyflow𝑓andany𝑠−𝑡cut 𝐴,𝐵 ,if𝑣 𝑓 =𝑐𝑎𝑝(𝐴,𝐵),then
1) 𝑓 is a max flow, and 2) 𝐴,𝐵 isamincut
Proof:
Let 𝑓∗ be a max flow, and 𝐴∗,𝐵∗ be a min cut
Let 𝑓 be any flow, and 𝐴,𝐵 be any 𝑠−𝑡 cut
𝑣 𝑓 ≤𝑣 𝑓∗ ≤𝑐𝑎𝑝 𝐴∗,𝐵∗ ≤𝑐𝑎𝑝 𝐴,𝐵
2021-02-24 CSC373 Winter 2021 – Sam Toueg 112

•
• •
Cuts and Flows
Consider any flow network F = (𝐺, 𝑠, 𝑡, 𝑐)
Lemma 3: For any flow 𝑓 and any 𝑠−𝑡 cut (𝐴,𝐵), 𝑣 𝑓 ≤ 𝑐𝑎𝑝(𝐴,𝐵) Corollary 4:
Foranyflow𝑓andany𝑠−𝑡cut 𝐴,𝐵 ,if𝑣 𝑓 =𝑐𝑎𝑝(𝐴,𝐵),then
1) 𝑓 is a max flow, and 2) 𝐴,𝐵 isamincut
Proof:
Let 𝑓∗ be a max flow, and 𝐴∗,𝐵∗ be a min cut
Let 𝑓 be any flow, and 𝐴,𝐵 be any 𝑠−𝑡 cut
𝑣 𝑓 ≤𝑣 𝑓∗ ≤𝑐𝑎𝑝 𝐴∗,𝐵∗ ≤𝑐𝑎𝑝 𝐴,𝐵
If𝑣 𝑓 =𝑐𝑎𝑝 𝐴,𝐵 then
𝑣𝑓 =𝑣𝑓∗ =𝑐𝑎𝑝𝐴∗,𝐵∗ =𝑐𝑎𝑝𝐴,𝐵 ∎
2021-02-24 CSC373 Winter 2021 – Sam Toueg 113

Correctness of Ford-Fulkerson Algorithm
• Theorem: Ford−Fulkerson algorithm outputs a maximum flow Proof:
Let 𝑓 be the flow returned by FF, and 𝐺3 be the corresponding residual graph 𝐴 = set of nodes that are reachable from 𝑠 in 𝐺3, 𝐵 = 𝑉 − 𝐴
𝐴,𝐵 isan𝑠-𝑡cutbecause𝑠∈𝐴and𝑡∈𝐵(bcsthereisno𝑠-𝑡pathin𝐺3!) Note that:
a) ∀ 𝑢,𝑣 ∈𝐸𝑠.𝑡. 𝑢∈𝐴, 𝑣∈𝐵: 𝑓 𝑢,𝑣 =𝑐(𝑢,𝑣)
Ø Otherwise 𝐺& has a forward edge 𝑢,𝑣 and then 𝑣 ∈ 𝐴 (but 𝑣 ∈ 𝐵!)
nodes reachable from 𝑠 𝐴 𝐵 in the final 𝐺&
𝑢𝑣 𝑠𝑡
nodes not reachable from 𝑠 in the final 𝐺&
𝑓𝑢,𝑣 =𝑐(𝑢,𝑣)
Otw: 𝐺 has a forward edge Otw: 𝐺! has a forward edge
𝑢, 𝑣
2021-02-24
So 𝑣 would be reachable from 𝑠! So 𝑣 would be reachable from 𝑠!
CSC373 Winter 2021 – Sam Toueg 115
!
𝑢, 𝑣

Correctness of Ford-Fulkerson Algorithm
• Theorem: Ford−Fulkerson algorithm outputs a maximum flow Proof:
Let 𝑓 be the flow returned by FF, and 𝐺3 be the corresponding residual graph 𝐴 = set of nodes that are reachable from 𝑠 in 𝐺3, 𝐵 = 𝑉 − 𝐴
𝐴,𝐵 isan𝑠-𝑡cutbecause𝑠∈𝐴and𝑡∈𝐵(bcsthereisno𝑠-𝑡pathin𝐺3!) Note that:
a) ∀ 𝑢,𝑣 ∈𝐸𝑠.𝑡. 𝑢∈𝐴, 𝑣∈𝐵: 𝑓 𝑢,𝑣 =𝑐(𝑢,𝑣)
b) ∀𝑣,𝑢 ∈𝐸𝑠.𝑡.𝑣∈𝐵,𝑢∈𝐴:𝑓𝑣,𝑢 =0
Ø Otherwise 𝐺& has a reverse edge (𝑢,𝑣) and then 𝑣 ∈ 𝐴 (but 𝑣 ∈ 𝐵!)
nodes reachable from 𝑠 𝐴 𝐵 in the final 𝐺&
nodes not reachable from 𝑠 in the final 𝐺&
𝑓𝑣,𝑢 =0
has a reverse edge
So 𝑣 would be reachable from 𝑠
So 𝑣 would be reachable from 𝑠 CSC373 Winter 2021 – Sam Toueg 116
𝑢𝑣 𝑠𝑡
Ow: 𝐺 !
𝑢, 𝑣
Ow: 𝐺 &
has a reverse edge 𝑢, 𝑣
2021-02-24

Correctness of Ford-Fulkerson Algorithm
• Theorem: Ford−Fulkerson algorithm outputs a maximum flow Proof:
Let 𝑓 be the flow returned by FF, and 𝐺3 be the corresponding residual graph 𝐴 = set of nodes that are reachable from 𝑠 in 𝐺3, 𝐵 = 𝑉 − 𝐴
𝐴,𝐵 isan𝑠-𝑡cutbecause𝑠∈𝐴and𝑡∈𝐵(bcsthereisno𝑠-𝑡pathin𝐺3!) Note that:
a) ∀ 𝑢,𝑣 ∈𝐸𝑠.𝑡. 𝑢∈𝐴, 𝑣∈𝐵: 𝑓 𝑢,𝑣 =𝑐(𝑢,𝑣)
b) ∀𝑣,𝑢 ∈𝐸𝑠.𝑡.𝑣∈𝐵,𝑢∈𝐴:𝑓𝑣,𝑢 =0
Ø Otherwise𝐺& hasareverseedge(𝑢,𝑣)andthen𝑣∈𝐴(but𝑣∈𝐵!)
nodes reachable from 𝑠 𝐴 𝐵
nodes not reachable from 𝑠 inthefinal𝐺&
inthefinal𝐺&
𝑓 𝑒 =𝑐(𝑒)
𝑒
𝑠𝑡 𝑒′
𝑓 𝑒′ = 0
2021-02-24
CSC373 Winter 2021 – Sam Toueg
117

Correctness of Ford-Fulkerson Algorithm
• Theorem: Ford−Fulkerson algorithm outputs a maximum flow Proof:
Let 𝑓 be the flow returned by FF, and 𝐺3 be the corresponding residual graph 𝐴 = set of nodes that are reachable from 𝑠 in 𝐺3, 𝐵 = 𝑉 − 𝐴
𝐴,𝐵 isan𝑠-𝑡cutbecause𝑠∈𝐴and𝑡∈𝐵(bcsthereisno𝑠-𝑡pathin𝐺3!) Note that:
a) ∀ 𝑢,𝑣 ∈𝐸𝑠.𝑡. 𝑢∈𝐴, 𝑣∈𝐵: 𝑓 𝑢,𝑣 =𝑐(𝑢,𝑣) b) ∀𝑣,𝑢 ∈𝐸𝑠.𝑡.𝑣∈𝐵,𝑢∈𝐴:𝑓𝑣,𝑢 =0
ByLemma2: 𝑣 𝑓 =𝑓#$% 𝐴 −𝑓!” 𝐴
= ∑$∈2,:∈7 𝑓 𝑢,𝑣 − ∑:∈7, $∈2 𝑓 𝑣,𝑢
= ∑$∈2,:∈7 𝑐(𝑢, 𝑣) − 0
= 𝑐𝑎𝑝 𝐴, 𝐵 By Corollary 4: 𝑓 is a max flow ∎
𝐴𝐵
𝑓𝑒 =𝑐(𝑒)
𝑒
𝑠𝑡
𝑒′
𝑓 𝑒′ = 0
Bonus: and 𝐴,𝐵 is a min cut ! 2021-02-24
CSC373 Winter 2021 – Sam Toueg
118

Max Flow – Min Cut Theorem
2021-02-24 CSC373 Winter 2021 – Sam Toueg 119

Max-Flow Min-Cut Theorem
From the FF algorithm and its proof we get the following theorems:
1. 2.
Max−Flow Min−Cut Theorem:
value of the max flow = capacity of the min cut
Integrality Theorem:
If all the edge capacities are integers,
there is an integral max flow 𝑓: 𝑓(𝑒) is an integer ∀𝑒 ∈ 𝐸
Ø But: not all max flows have integer 𝑓 𝑒 &s
𝑎 𝑠
1
𝑎
1
0.5/1
0.5/1
0.5/1
1/1
𝑡
𝑐1𝑡𝑠 𝑏 max flow = 1
F = (𝐺,𝑠,𝑡,𝑐)
𝑐 𝑏
11
0.5/1
2021-02-24 CSC373 Winter 2021 – Sam Toueg
121

Max-Flow Min-Cut Theorem
From the FF algorithm and its proof we get the following theorems:
1. 2.
Max−Flow Min−Cut Theorem:
value of the max flow = capacity of the min cut
Integrality Theorem:
If all the edge capacities are integers,
there is an integral max flow 𝑓: 𝑓(𝑒) is an integer ∀𝑒 ∈ 𝐸
Ø But: not all max flows have integer 𝑓 𝑒 &s
𝑎 𝑠
1
1/1 𝑎
0/1
integral flow
1
1/1
1/1
𝑡
𝑐1𝑡𝑠 max flow = 1
𝑐
11
𝑏
F = (𝐺,𝑠,𝑡,𝑐)
𝑏
0/1
2021-02-24
CSC373 Winter 2021 – Sam Toueg
122

Min Cut Problem
• Problem
ØInput: flow network F = (𝐺, 𝑠, 𝑡, 𝑐) ØOutput: 𝑠-𝑡 cut (𝐴, 𝐵) of min capacity
i.e., ∀ 𝑠−𝑡 cut 𝑆,𝑇 ,𝑐𝑎𝑝 𝐴,𝐵 ≤ 𝑐𝑎𝑝(𝑆,𝑇) Min-Cut(F):
𝑓 ← Ford−Fulkerson(F) compute residual graph 𝐺3
𝐴 = {all nodes that are reachable from 𝑠 in 𝐺3} 𝐵=𝑉−𝐴
return (𝐴, 𝐵)
Running time = Running time of Ford−Fulkerson algorithm
2021-02-24 CSC373 Winter 2021 – Sam Toueg 123

Related Posts