March 5, 2009
4
March 5, 2009
5
March 5, 2009
6
Analysis of Algorithms Recall from previous Lecture • Flow value: | f | = f (s, V).
Max-flow, min-cut theorem
Proof (continued)
Ford-Fulkerson max-flow
Ford-Fulkerson max-flow
LECTURE 26-27 • Cut: Any partition (S, T) of V such that s ∈ S Network Flows II andt∈T.
Theorem. The following are equivalent: 1. |f|=c(S,T)forsomecut(S,T).
2. f is a maximum flow.
3. fadmitsnoaugmentingpaths.
• Max flow-min cut (proof) • Lemma. | f | = f (S, T) for any cut (S, T).
• Ford-Fulkerson algorithm • Corollary. | f | ≤ c(S, T) for any cut (S, T). •Edmonds-Karpalgorithm •Residualgraph:ThegraphGf =(V,Ef)with
Proof. (1)⇒(2):Since|f|≤c(S,T)foranycut(S,T)(by the corollary from Lecture 22), the assumption that | f | = c(S, T) implies that f is a maximum flow.
strictly positive residual capacities cf (u, v) = • Monotonocity lemma c(u,v)–f(u,v)>0.
• Bounding augmentations • Augmenting path: Any path from s to t in Gf . • Residual capacity of an augmenting path:
(2) ⇒ (3): If there were an augmenting path, the flow value could be increased, contradicting the maximality of f.
(3) ⇒ (1): Suppose that f admits no augmenting paths. DefineS={v∈V:thereexistsapathinGf fromstov}, andletT=V–S. Observethats∈Sandt∈T,andthus (S, T) is a cut. Consider any vertices u ∈ S and v ∈ T.
algorithm
algorithm
s u v
10 10 0:10 0:10
path in Gf S T
G:s 1 t G:s 0:1 t st st
Wemusthavecf (u,v)=0,sinceifcf (u,v)>0,thenv∈S, not v ∈ T as assumed. Thus, f(u, v) = c(u, v), since cf (u, v) =c(u,v)–f(u,v). Summingoverallu∈Sandv∈T yields f(S, T) = c(S, T), and since | f | = f(S, T), the theorem follows.
109 109
0:109
0:109
Ford-Fulkerson max-flow
Ford-Fulkerson max-flow
Ford-Fulkerson max-flow
algorithm
algorithm
algorithm
Algorithm:
Algorithm:
Algorithm:
f [u, v] ← 0 for all u, v ∈ V
while an augmenting path p in G wrt f exists
f [u, v] ← 0 for all u, v ∈ V
while an augmenting path p in G wrt f exists
f [u, v] ← 0 for all u, v ∈ V
while an augmenting path p in G wrt f exists
doaugment f bycf(p) Can be slow:
doaugment f bycf(p) Can be slow:
doaugment f bycf(p) Can be slow:
March 5, 2009
7 March 5, 2009
8 March 5, 2009
9
0:109 0:109 G:s 0:1 t
1:109 0:109
1:109 0:109
March 5, 2009
2
March 5, 2009 3
Algorithm:
Algorithm:
cf (p) = min {cf (u,v)}. (u,v)∈p
f [u, v] ← 0 for all u, v ∈ V
while an augmenting path p in G wrt f exists
f [u, v] ← 0 for all u, v ∈ V
while an augmenting path p in G wrt f exists
do augment f by cf (p) Can be slow:
do augment f by cf (p) Can be slow:
suv9999
G:s 1:1 t ststst
0:109 0:109
0:109 1:109
G:s 1:1 t 0:109 1:109
March 5, 2009
10
March 5, 2009
11
March 5, 2009
12
Ford-Fulkerson max-flow
Ford-Fulkerson max-flow
Ford-Fulkerson max-flow
algorithm
algorithm
algorithm
Algorithm:
Algorithm:
Algorithm:
f [u, v] ← 0 for all u, v ∈ V
while an augmenting path p in G wrt f exists
f [u, v] ← 0 for all u, v ∈ V
while an augmenting path p in G wrt f exists
f [u, v] ← 0 for all u, v ∈ V
while an augmenting path p in G wrt f exists
doaugment f bycf(p) Can be slow:
doaugment f bycf(p) Can be slow:
doaugment f bycf(p) Can be slow:
1:109
1:109
1:109
(In independent work, Dinic also gave polynomial- time bounds.)
For the inductive case, consider a breadth-first path s → L→u→vinGf′. Wemusthaveδ′(v)=δ′(u)+1,since subpaths of shortest paths are shortest paths. Certainly, (u, v) ∈ Ef ′ , and now consider two cases depending on whether (u, v) ∈ Ef .
March 5, 2009
13
March 5, 2009 14
March 5, 2009 15
Case 2
Counting flow augmentations
Counting flow augmentations
Case: (u, v) ∉ Ef .
Since (u, v) ∈ Ef ′ , the augmenting path p that produced
Theorem. The number of flow augmentations
Theorem. The number of flow augmentations
in the Edmonds-Karp algorithm (Ford-Fulkerson with breadth-first augmenting paths) is O(V E). Proof. Let p be an augmenting path, and suppose that the residual capacity of edge (u, v) ∈ p is cf (u, v) = cf (p). Then, we say (u, v) is critical, and it disappears from the residual graph after flow augmentation.
Example:
f ′ from f must have included (v, u). Moreover, p is a breadth-first path in Gf :
with breadth-first augmenting paths) is O(V E).
p=s→L→v→u→L→t. Thus, we have
Proof. Let p be an augmenting path, and suppose that
δ(v) = δ(u) – 1 ≤ δ′(u) – 1 ≤ δ′(v) – 2
(breadth-first path) (induction) (breadth-first path)
residual graph after flow augmentation.
< δ′(v) ,
G:stG:st fstf′st
thereby establishing monotonicity for this case, too. March 5, 2009
32 12
54434
16
March 5, 2009
17 March 5, 2009
18
1:109
G:s 0:1 t
2:109 1:109
G:s 1:1 t ststst
G:s 0:1 t 1:109 1:109
1:109 1:109
1:109 2:109
2 billion iterations on a graph with 4 vertices!
Edmonds-Karp algorithm
Monotonicity lemma
Case 1
Edmonds and Karp noticed that many people’s implementations of Ford-Fulkerson augment along a breadth-first augmenting path: a shortest path in Gf from s to t where each edge has weight 1. These implementations would always run relatively fast.
Lemma. Let δ(v) = δf (s, v) be the breadth-first distance from s to v in Gf . During the Edmonds- Karp algorithm, δ(v) increases monotonically.
Case: (u, v) ∈ Ef . We have
Since a breadth-first augmenting path can be found in O(E) time, their analysis, which provided the first polynomial-time bound on maximum flow, focuses on bounding the number of flow augmentations.
show that δ′(v) ≥ δ(v) by induction on δ(v). For the base case, δ′(s) = δ(s) = 0.
= δ′(v)
and thus monotonicity of δ(v) is established.
Proof. Suppose that f is a flow on G, and augmentation produces a new flow f ′. Let δ′(v) = δf ′(s, v). We’ll
δ(v) ≤ δ(u) + 1 ≤ δ′(u) + 1
(triangle inequality) (induction) (breadth-first path),
in the Edmonds-Karp algorithm (Ford-Fulkerson
wehavecf(u,v)=cf(p)foredge(u,v)∈p. Then,we
say that (u, v) is critical, and it disappears from the
Example:
cf (p) = 2
24723
25 1
Example:
Example:
Example:
March 5, 2009
19
March 5, 2009
20
March 5, 2009
21
Counting flow augmentations (continued)
Counting flow augmentations (continued)
Counting flow augmentations (continued)
The first time an edge (u, v) is critical, we have δ(v) = δ(u) + 1, since p is a breadth-first path. We must wait until (v, u) is on an augmenting path before (u, v) can be critical again. Let δ′ be the distance function when (v, u) is on an augmenting path. Then, we have
The first time an edge (u, v) is critical, we have δ(v) = δ(u) + 1, since p is a breadth-first path. We must wait until (v, u) is on an augmenting path before (u, v) can be critical again. Let δ′ be the distance function when (v, u) is on an augmenting path. Then, we have
The first time an edge (u, v) is critical, we have δ(v) = δ(u) + 1, since p is a breadth-first path. We must wait until (v, u) is on an augmenting path before (u, v) can be critical again. Let δ′ be the distance function when (v, u) is on an augmenting path. Then, we have
δ′(u) = δ′(v) + 1 ≥ δ(v) + 1 = δ(u) + 2
(breadth-first path) (monotonicity) (breadth-first path).
δ′(u) = δ′(v) + 1 ≥ δ(v) + 1 = δ(u) + 2
(breadth-first path) (monotonicity) (breadth-first path).
δ′(u) = δ′(v) + 1 ≥ δ(v) + 1 = δ(u) + 2
(breadth-first path) (monotonicity) (breadth-first path).
δ(u) = 5 u uuu
δ(u) = 5 u
s tt s tt s tt
u
sss
vvv
v
δ(v) = 6 v
δ(v) = 6 v
Counting flow augmentations (continued)
Counting flow augmentations (continued)
Counting flow augmentations (continued)
The first time an edge (u, v) is critical, we have δ(v) = δ(u) + 1, since p is a breadth-first path. We must wait until (v, u) is on an augmenting path before (u, v) can be critical again. Let δ′ be the distance function when (v, u) is on an augmenting path. Then, we have
The first time an edge (u, v) is critical, we have δ(v) = δ(u) + 1, since p is a breadth-first path. We must wait until (v, u) is on an augmenting path before (u, v) can be critical again. Let δ′ be the distance function when (v, u) is on an augmenting path. Then, we have
The first time an edge (u, v) is critical, we have δ(v) = δ(u) + 1, since p is a breadth-first path. We must wait until (v, u) is on an augmenting path before (u, v) can be critical again. Let δ′ be the distance function when (v, u) is on an augmenting path. Then, we have
δ′(u) = δ′(v) + 1 ≥ δ(v) + 1 = δ(u) + 2
(breadth-first path) (monotonicity) (breadth-first path).
δ′(u) = δ′(v) + 1 ≥ δ(v) + 1 = δ(u) + 2
(breadth-first path) (monotonicity) (breadth-first path).
δ′(u) = δ′(v) + 1 ≥ δ(v) + 1 = δ(u) + 2
(breadth-first path) (monotonicity) (breadth-first path).
Example: δ(u) ≥ 7 u
Example:
Example:
Running time of Edmonds-
Best to date
Karp
Distances start out nonnegative, never decrease, and are at most |V| – 1 until the vertex becomes unreachable. Thus, (u, v) occurs as a critical edge O(V) times, because δ(v) increases by at least 2 between occurrences. Since the residual graph contains O(E) edges, the number of flow augmentations is O(V E).
• The asymptotically fastest algorithm to date for maximum flow, due to King, Rao, and Tarjan, runs in O(V E logE/(V lg V)V) time.
Corollary. The Edmonds-Karp maximum-flow algorithm runs in O(V E2) time.
O(min{V 2/3, E 1/2} ⋅ E lg (V 2/E + 2) ⋅ lg C), where C is the maximum capacity of any edge in the graph.
Proof. Breadth-first search runs in O(E) time, and all other bookkeeping is O(V) per augmentation.
March 5, 2009 25
March 5, 2009 26
δ(u) ≥ 7 u uuu
δ(u) ≥ 7 u
s tt s tt s tt
sss
δ(v)≥6 v
March 5, 2009 22
δ(v)≥6 v
δ(v)≥8 v
vvv
March 5, 2009
23 March 5, 2009
24
• If we allow running times as a function of edge weights, the fastest algorithm for maximum flow, due to Goldberg and Rao, runs in time