Lecture 10 – Edmonds-Karp
The University of Sydney
Page 1
Ford Fulkerson
Ford-Fulkerson(G,s,t) { foreach e Î 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.
Û
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/e
Set x = m ln F Þ F × (1-1/m)m ln F < F × (1/e)ln F < 1 The University of Sydney
Page 26
Choosing Good Augmenting Paths
– Ford Fulkerson
Choose 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 path
The University of Sydney Page 27