Introduction to Algorithms 6.046J/18.401J/SMA5503 Lecture 23 Prof. Charles E. Leiserson Introduction to Algorithms Day 40 L23.2? 2001 by Charles E. Leiserson Recall from Lecture 22 ? Flow value: | f | = f (s, V). ? Cut: Any partition (S, T) of V such that s ∈ S and t ∈ T. ? Lemma. | f | = f (S, T) for any cut (S, T). ? Corollary. | f | ≤ c(S, T) for any cut (S, T). ? Residual graph: The graph G f = (V, E f ) with strictly positive residual capacities c f (u, v) = c(u, v) – f (u, v) > 0. ? Augmenting path: Any path from s to t in G f . ? Residual capacity of an augmenting path: )},({min)( ),( vucpc f pvu f ∈ = . Introduction to Algorithms Day 40 L23.3? 2001 by Charles E. Leiserson Max-flow, min-cut theorem Theorem. The following are equivalent: 1. | f | = c(S, T) for some cut (S, T). 2. f is a maximum flow. 3. f admits no augmenting paths. Proof. (1) ? (2): Since | f | ≤ c(S, T) for any cut (S, T) (by the corollary from Lecture 22), the assumption that | f | = c(S, T) implies that f is a maximum flow. (2) ? (3): If there were an augmenting path, the flow value could be increased, contradicting the maximality of f. Introduction to Algorithms Day 40 L23.4? 2001 by Charles E. Leiserson Proof (continued) (3) ? (1): Suppose that f admits no augmenting paths. Define S = {v ∈ V : there exists a path in G f from s to v}, and let T = V – S. Observe that s ∈ S and t ∈ T, and thus (S, T) is a cut. Consider any vertices u ∈ S and v ∈ T. We must have c f (u, v) = 0, since if c f (u, v) > 0, then v ∈ S, not v ∈ T as assumed. Thus, f (u, v) = c(u, v), since c f (u, v) = c(u, v) – f (u, v). Summing over all u ∈ S and v ∈ T yields f (S, T) = c(S, T), and since | f | = f (S, T), the theorem follows. s s u u v v ST path in G f Introduction to Algorithms Day 40 L23.5? 2001 by Charles E. Leiserson Ford-Fulkerson max-flow algorithm Algorithm: f [u, v] ← 0 for all u, v ∈ V while an augmenting path p in G wrt f exists do augment f by c f (p) Can be slow: s s t t 10 9 10 9 10 9 1 10 9 G: Introduction to Algorithms Day 40 L23.6? 2001 by Charles E. Leiserson Ford-Fulkerson max-flow algorithm Can be slow: s s t t 0:10 9 0:10 9 0:10 9 0:1 0:10 9 G: Algorithm: f [u, v] ← 0 for all u, v ∈ V while an augmenting path p in G wrt f exists do augment f by c f (p) Introduction to Algorithms Day 40 L23.7? 2001 by Charles E. Leiserson Ford-Fulkerson max-flow algorithm Can be slow: s s t t 0:10 9 0:10 9 0:10 9 0:1 0:10 9 G: Algorithm: f [u, v] ← 0 for all u, v ∈ V while an augmenting path p in G wrt f exists do augment f by c f (p) Introduction to Algorithms Day 40 L23.8? 2001 by Charles E. Leiserson Ford-Fulkerson max-flow algorithm Can be slow: s s t t 1:10 9 0:10 9 1:10 9 1:1 0:10 9 G: Algorithm: f [u, v] ← 0 for all u, v ∈ V while an augmenting path p in G wrt f exists do augment f by c f (p) Introduction to Algorithms Day 40 L23.9? 2001 by Charles E. Leiserson Ford-Fulkerson max-flow algorithm Can be slow: s s t t 1:10 9 0:10 9 1:10 9 1:1 0:10 9 G: Algorithm: f [u, v] ← 0 for all u, v ∈ V while an augmenting path p in G wrt f exists do augment f by c f (p) Introduction to Algorithms Day 40 L23.10? 2001 by Charles E. Leiserson Ford-Fulkerson max-flow algorithm Can be slow: s s t t 1:10 9 1:10 9 1:10 9 0:1 1:10 9 G: Algorithm: f [u, v] ← 0 for all u, v ∈ V while an augmenting path p in G wrt f exists do augment f by c f (p) Introduction to Algorithms Day 40 L23.11? 2001 by Charles E. Leiserson Ford-Fulkerson max-flow algorithm Can be slow: s s t t 1:10 9 1:10 9 1:10 9 0:1 1:10 9 G: Algorithm: f [u, v] ← 0 for all u, v ∈ V while an augmenting path p in G wrt f exists do augment f by c f (p) Introduction to Algorithms Day 40 L23.12? 2001 by Charles E. Leiserson Ford-Fulkerson max-flow algorithm Can be slow: s s t t 2:10 9 1:10 9 2:10 9 1:1 1:10 9 G: 2 billion iterations on a graph with 4 vertices! Algorithm: f [u, v] ← 0 for all u, v ∈ V while an augmenting path p in G wrt f exists do augment f by c f (p) Introduction to Algorithms Day 40 L23.13? 2001 by Charles E. Leiserson Edmonds-Karp algorithm Edmonds and Karp noticed that many people’s implementations of Ford-Fulkerson augment along a breadth-first augmenting path: a shortest path in G f from s to t where each edge has weight 1. These implementations would always run relatively fast. 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. (In independent work, Dinic also gave polynomial- time bounds.) Introduction to Algorithms Day 40 L23.14? 2001 by Charles E. Leiserson Monotonicity lemma Lemma. Let δ(v) = δ f (s, v) be the breadth-first distance from s to v in G f . During the Edmonds- Karp algorithm, δ(v) increases monotonically. Proof. Suppose that f is a flow on G, and augmentation produces a new flow f′. Let δ′(v) = δ f ′ (s, v). We’ll show that δ′(v) ≥δ(v) by induction on δ(v). For the base case, δ′(s) =δ(s) = 0. For the inductive case, consider a breadth-first path s → L→ u → v in G f ′ . We must have δ′(v) = δ′(u) + 1, since subpaths of shortest paths are shortest paths. Certainly, (u, v) ∈ E f ′ , and now consider two cases depending on whether (u, v) ∈ E f . Introduction to Algorithms Day 40 L23.15? 2001 by Charles E. Leiserson Case 1 Case: (u, v) ∈ E f . δ(v) ≤δ(u) + 1 (triangle inequality) ≤δ′(u) + 1 (induction) = δ′(v) (breadth-first path), and thus monotonicity of δ(v) is established. We have Introduction to Algorithms Day 40 L23.16? 2001 by Charles E. Leiserson Case 2 Case: (u, v) ? E f . Since (u, v) ∈ E f ′ , the augmenting path p that produced f′ from f must have included (v, u). Moreover, p is a breadth-first path in G f : p = s →L→ v → u →L→ t . Thus, we have δ(v) =δ(u) – 1 (breadth-first path) ≤δ′(u) – 1 (induction) ≤δ′(v) – 2 (breadth-first path) < δ′(v) , thereby establishing monotonicity for this case, too. Introduction to Algorithms Day 40 L23.17? 2001 by Charles E. Leiserson Counting flow augmentations Theorem. The number of flow augmentations in the Edmonds-Karp algorithm (Ford-Fulkerson with breadth-first augmenting paths) is O(VE). Proof. Let p be an augmenting path, and suppose that we have c f (u, v) = c f (p) for edge (u, v) ∈ p. Then, we say that (u, v) is critical, and it disappears from the residual graph after flow augmentation. s s 2 3 G f : 4 2 7 2 1 t t 3 c f (p) = 2 Example: 2 Introduction to Algorithms Day 40 L23.18? 2001 by Charles E. Leiserson Counting flow augmentations Theorem. The number of flow augmentations in the Edmonds-Karp algorithm (Ford-Fulkerson with breadth-first augmenting paths) is O(VE). Proof. Let p be an augmenting path, and suppose that the residual capacity of edge (u, v) ∈ p is c f (u, v) = c f (p). Then, we say (u, v) is critical, and it disappears from the residual graph after flow augmentation. s s 5 G f ′ : 2 4 5 3 t t 1 Example: 44 Introduction to Algorithms Day 40 L23.19? 2001 by Charles E. Leiserson 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 s s u u v v t t Example: δ′(u) =δ′(v) + 1 (breadth-first path) ≥δ(v) + 1 (monotonicity) =δ(u) + 2 (breadth-first path). Introduction to Algorithms Day 40 L23.20? 2001 by Charles E. Leiserson 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 δ′(u) =δ′(v) + 1 (breadth-first path) ≥δ(v) + 1 (monotonicity) =δ(u) + 2 (breadth-first path). s s u u v v t t δ(u) = 5 δ(v) = 6 Example: Introduction to Algorithms Day 40 L23.21? 2001 by Charles E. Leiserson 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 s s u u v v t t δ(u) = 5 δ(v) = 6 Example: δ′(u) =δ′(v) + 1 (breadth-first path) ≥δ(v) + 1 (monotonicity) =δ(u) + 2 (breadth-first path). Introduction to Algorithms Day 40 L23.22? 2001 by Charles E. Leiserson 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 s s u u v v t t δ(u) ≥ 7 δ(v) ≥ 6 Example: δ′(u) =δ′(v) + 1 (breadth-first path) ≥δ(v) + 1 (monotonicity) =δ(u) + 2 (breadth-first path). Introduction to Algorithms Day 40 L23.23? 2001 by Charles E. Leiserson 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 s s u u v v t t δ(u) ≥ 7 δ(v) ≥ 6 Example: δ′(u) =δ′(v) + 1 (breadth-first path) ≥δ(v) + 1 (monotonicity) =δ(u) + 2 (breadth-first path). Introduction to Algorithms Day 40 L23.24? 2001 by Charles E. Leiserson 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 s s u u v v t t δ(u) ≥ 7 δ(v) ≥ 8 Example: δ′(u) =δ′(v) + 1 (breadth-first path) ≥δ(v) + 1 (monotonicity) =δ(u) + 2 (breadth-first path). Introduction to Algorithms Day 40 L23.25? 2001 by Charles E. Leiserson Running time of Edmonds- 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(VE). Corollary. The Edmonds-Karp maximum-flow algorithm runs in O(VE 2 ) time. Proof. Breadth-first search runs in O(E) time, and all other bookkeeping is O(V) per augmentation. Introduction to Algorithms Day 40 L23.26? 2001 by Charles E. Leiserson Best to date ? The asymptotically fastest algorithm to date for maximum flow, due to King, Rao, and Tarjan, runs in O(VElog E/(V lg V) V) time. ? 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 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.