Network Flow and Matching

Design and Analysis of Algorithms Massachusetts Institute of Technology Profs. Erik Demaine, Srini Devadas and Nancy Lynch April 3, 2015 6.046J/18.410J Recitation 7 Network Flow and Matching Edmonds-Karp Analysis Recall: Edmonds-Karp is an efficient implementation of the Ford-Fulkerson method which selects shortest augmenting paths in the residual graph. It assigns a weight of 1 to every edge and runs BFS to find a breadth-first shortest path from s to t in Gf . Monotonicity Lemma Lemma. Let δ(v) = δf (s, v) be the breadth-first distance from s to v in Gf . During the EdmondsKarp algorithm, δ(v) increases monotonically. Proof: Suppose that augmenting a flow f on G produces a new flow f / . Let δ / (v) = δf ' (s, v). We will show that δ / (v) ≥ δ(v) by induction on δ / (v). Base Case: δ / (v) = 0. This implies that v = s, and since δ(s) = 0 and distance can never be negative, it follows δ / (s) ≥ δ(s). Inductive Case: Assume inductive hypothesis holds for any u where δ / (u) < δ / (v). We will show that it is also hods for v. Consider a breadth-first path s → · · · → u → v in Gf ' . We must have δ / (v) = δ / (u) + 1, since subpaths of shortest paths are also shortest paths. Also note that by our inductive assumption δ / (u) ≥ δ(u), because δ / (u) < δ / (v). Certainly, (u, v) ∈ Ef ' . We will now prove that δ / (v) ≥ δ(v) in both cases where (u, v) ∈ Ef and (u, v) ∈ Ef . Case 1: (u, v) ∈ Ef . Here we have: δ(v) ≤ δ(u) + 1 triangle inequality ≤ δ / (u) + 1 inductive assumption = δ / (v) breadth-first path Therefore δ / (v) ≥ δ(v) and monotonicity of δ(v) is established. (1) 2 Recitation 7: Network Flow and Matching Case 2: (u, v) ∈ Ef . Here, the only way (u, v) ∈ Ef ' is if the augmenting path p that produced f / from f must have included (v, u). Moreover, p is a breadth first path in Gf : p = s → ··· → v → u Thus, we have: δ(v) = δ(u) − 1 breadth-first path ≤ δ / (u) − 1 inductive assumption = δ / (v) − 2 breadth-first path < δ / (v) (2) thereby establishing monotonicity for this case, too. D Counting Flow Augmentations Theorem. The number of flow augmentations in the Edmonds-Karp algorithm is O(V E). Proof: For an augmenting path p, define cf (p) = min{cf (u, v) ∈ p}. Let p be an augmenting path, and suppose that we have cf (p) = cf (u, v) for edge (u, v) ∈ p. Then, we say that (u, v) is critical, and it disappears from the residual graph after flow augmentation. This is because during augmentation, the residual capacity of every edge in p decreases by cf (p) as that much new flow is pushed through the augmenting path. And since cf (u, v) − cf (p) = 0, the edge disappears after augmentation. The first time an edge (u, v) is critical, we have δ(v) = δ(u)+1 since p is a breadth-first path. After the augmentation, we must wait until (v, u) is on an augmenting path before (u, v) can be critical again. Let δ / be the distance function in the residual network 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 (3) Hence between each occurrence of an edge (u, v) as critical, δ(u) increases by at least 2. And since δ(u) starts out non-negative and can be at most |V | − 1 until the vertex is unreachable, each edge can be critical O(V ) times. And since the residual graph contains O(E) edges, the total number of flow augmentations is O(V E). D Corollary. The Edmonds-Karp maximum-flow algorithm runs in O(V E 2 ) time. Proof: Breadth-First Search runs in O(E) time, and there are O(V E) augmentations. All other bookkeeping is O(V ) per augmentation. Recitation 7: Network Flow and Matching 3 Applications of Network Flow Vertex Cover Given an undirected graph G = (V, E), we say that a set S ⊆ V of vertices covers G, if for every edge (u, v) ∈ E, S contains either u or v. The Vertex Cover problem is now to find S such that S covers G and |S| is minimal. Vertex Cover is NP-Hard in general graphs but polynomial time solvable in bipartite graphs. Bipartite Vertex Cover Given a bipartite graph G = (L U R, E ⊆ L × R), find the set S such that S covers G and |S| is minimal. Solution: Given G, define the following Flow Network H: • Create a new source vertex s and add edges of capacity 1 from s to every vertex in L • Create a new sink vertex t and add edges of capacity 1 from every vertex in R to t • Direct all edges in E from L to R and assign each edge ∞ capacity Run Maximum Flow in H and return the value. For example, consider the following graph H constructed from G = ({L1 , L2 , L3 }U{R1 , R2 , R3 }, E) where E consists of the shown edges: ∞ L1 R1 1 ∞ 1 1 s 1 ∞ L2 R2 ∞ 1 t 1 L3 R3 ∞ In this example, the Maximum Flow is 2, and the minimal vertex cover is Q = {L1 , R3 } and |Q| = 2. 4 Recitation 7: Network Flow and Matching Correctness of Bipartite Vertex Cover as Maximum Flow Claim 1: Every Vertex Cover Q of H defines an (S, T ) cut of a finite value c(S, T ). Proof: Let Q = QL U QR where QL = Q ∩ L and QR = Q ∩ R. Then define the cut (S, T ) as follows: S = {s} ∪ QR ∪ (L\QL ) T = {t} ∪ QL ∪ (R\QR ) Proof by picture: QL R\QR t s L\QL QR Note that there cannot be any edges going from L\QL to R\QR because if there were such an edge, both endpoint vertices would not be covered and would contradict that Q was a valid vertex cover. From the picture it is clear that (S, T ) is indeed a cut in H. It is also clear that c(S, T ) = QL + QR because the only edges that cross the cut (S, T ) are all the edges from s to QL and from QR to t, and each of them have capacity 1. D Claim 1 implies that c(S ∗ , T ∗ ) ≤ |Q∗ | where Q∗ is the minimum Vertex Cover of G and (S ∗ , T ∗ ) is the minimum cut in H. Claim 2: For any finite cut (S, T ) in H, the set Q = (S ∩ R) ∪ (T ∩ L) is a Vertex Cover of G. Proof: Observe the following picture: Recitation 7: Network Flow and Matching T ∩L 5 T ∩R t s S∩L S∩R Note that there cannot be any edges going from S ∩ L to T ∩ R because that would make c(S, T ) infinite and contradict the assumption that the cut must be of finite capacity. From this picture, it is clear that every edge in G has at least one end point in either T ∩ L or S ∩ R and indeed Q = (S ∩ R) ∪ (T ∩ L) covers G. It is also clear that |Q| = |S ∩ R| + |T ∩ L| = c(S, T ). D Claim 2 implies that |Q∗ | ≤ c(S ∗ , T ∗ ) where (S ∗ , T ∗ ) is the minimum cut in H and Q∗ is the minimum Vertex Cover of G. Punchline: By claims 1 and 2, the size of the minimum Vertex Cover of G, |Q∗ | is equal to the size of minimum cut (S ∗ , T ∗ ). And since the Maximum Flow is equal to the Minimum Cut, we can use Maximum Flow to solve Bipartite Vertex Cover in the way described above.