[SOLVED] CS Lecture 10 Edmonds-Karp

Lecture 10 Edmonds-Karp
The University of Sydney
Page 1

Ford Fulkerson
Ford-Fulkerson(G,s,t) { foreach e I E
f(e) 0
Gf residual graph
while (there exists augmenting path P in Gf){ f Augment(f,P)
update Gf }
return f }
Choose any augmenting path (F iterations in the worst-case)
The University of Sydney Page 17

Worst-case instance for arbitrary augmenting path
1
1X0 0
DD
s 1X01 t
D
D
0 X01 2
The University of Sydney
Page 18

Worst-case instance for arbitrary augmenting path
11
1 X0 0 1 X0 X0 1 DDDD
s 1X01 t s 1X0X10 t DDDD
0 X01 10 X01 X
22
Flow value increases by exactly 1 per augmentation
The University of Sydney
Page 19

Worst-case instance for arbitrary augmenting path
11
1 X0 0 1 X0 X0 1 DDDD
s 1X01 t s 1X0X10 t DDDD
0 X01 10 X01 X
22
If we had chosen either max bottleneck path or shortest path,
only 1 augmentation needed!
The University of Sydney Page 20

Choosing Good Augmenting Paths
Ford Fulkerson
Choose any augmenting path (F iterations)
Edmonds Karp #1 (m log F iterations) Choose max bottleneck path (This lecture)
Improved Edmonds Karp #1 (m log F iterations)
Choose approximate max bottleneck path [capacity scaling]
Edmonds Karp #2 (nm iterations) [Edmonds-Karp 1972, Dinitz 1970] Choose minimum link path (This lecture)
The University of Sydney Page 21

Edmonds-Karp #1
Pick the augmenting path with largest capacity [maximum bottleneck path]
The University of Sydney Page 22

Edmonds-Karp #1
Pick the augmenting path with largest capacity [maximum bottleneck path]
Claim: If maximum flow in G is F, there must exists a path from s to t with capacity at least F/m.
The University of Sydney Page 23

Edmonds-Karp #1
Pick the augmenting path with largest capacity [maximum bottleneck path]
Claim: If maximum flow in G is F, there must exists a path from s to t with capacity at least F/m.
Proof:
Delete all edges of capacity less than F/m.
Is the graph still connected?
F=24 m=15
6 10 t
2 9
15 s 5 3 8
5
15 10
10
4
15
4 6 15 4 30 7
10
The University of Sydney
Page 24

Edmonds-Karp #1
Pick the augmenting path with largest capacity [maximum bottleneck path]
Claim: If maximum flow in G is F, there must exists a path from s to t with capacity at least F/m.
Proof:
Delete all edges of capacity less than F/m.
Is the graph still connected?
Yes, otherwise we have a cut of value less than F.
The remaining graph must have a path from s to t and since all edges have capacity at least F/m, the path itself has capacity at least F/m.
The University of Sydney
Page 25

Edmonds-Karp #1
Theorem: Edmonds-Karp #1 makes at most O(m log F) iterations.
Proof:
At least 1/m of remaining flow is added in each iteration.
U
Remaining flow reduced by a factor of (1-1/m) per iteration. #iterations until remaining flow <1? F(1-1/m)x <1?We know: (1-1/m)m <1/eSet x = m ln F F (1-1/m)m ln F < F (1/e)ln F < 1 The University of SydneyPage 26 Choosing Good Augmenting Paths Ford FulkersonChoose any augmenting path (F iterations) Edmonds Karp #1 (m log F iterations) Choose max flow path Improved Ford Fulkerson (m log F iterations)Choose approximate max flow path [capacity scaling] Edmonds Karp #2 (nm iterations) [Edmonds-Karp 1972, Dinitz 1970] Choose minimum link pathThe University of Sydney Page 27