11/14/2008 A. Smith; based on slides by K. Wayne and S. Raskhodnikova A. Smith Algorithm Design and Analysis LECTURE 28 Network Flow •Choosing good augmenting paths •Capacity scaling algorithmPre-break: Ford-Fulkerson • Find max s-t flow & min s-t cut in O(mnC) time – All capacities are integers  C –(Today: removing this assumption) •Duality: Max flow value = min cut capacity •Integrality: if capacities are integers, then FF algorithm produces an integral max flow 10/22/2008 A. Smith; based on slides by S. Raskhodnikova and K. WayneResidual Graph Original edge: e = (u, v)  E.  Flow f(e), capacity c(e). Residual edge.  "Undo" flow sent.  e = (u, v) and eR = (v, u).  Residual capacity: Residual graph: Gf = (V, Ef ).  Residual edges with positive residual capacity.  Ef = {e : f(e) < c(e)}  {eR : c(e) > 0}. u v 17 6 capacity u v 11 residual capacity 6 residual capacity flowFord-Fulkerson Summary Ford-Fulkerson: • While you can, • Greedily push flow • Update residual graph Theorem: FF algorithm terminates with a maximum flow. Two big ideas: a) Max flow  min cut b) Value(FF output flow) = capacity(some cut) Hence… FF flow is maximal and the corresponding cut is minimal. Proof of (b): •f = flow output by FF algorithm •A = set of vertices reachable from s in residual graph Gf •Lemma: value(f) = capacity(A) (see Lecture 22) original network s t AB1 X X X 1 0 1 Ford-Fulkerson: Exponential Number of Augmentations Q. Is generic Ford-Fulkerson algorithm polynomial in input size? A. No. If max capacity is C, then algorithm can take C iterations. s 1 2 t C C 0 0 0 0 0 C C 1 s 1 2 t C C 1 0 0 0 0 0 X C C X X X 1 1 1 X X 1 1 m, n, and log CChoosing Good Augmenting Paths Use care when selecting augmenting paths.  Some choices lead to exponential algorithms.  Clever choices lead to polynomial algorithms.  If capacities are irrational, algorithm not guaranteed to terminate! Goal: choose augmenting paths so that:  Can find augmenting paths efficiently.  Few iterations. Choose augmenting paths with: [Edmonds-Karp 1972, Dinitz 1970]  Max bottleneck capacity.  Sufficiently large bottleneck capacity.  Fewest number of edges.Capacity Scaling Intuition. Choosing path with highest bottleneck capacity increases flow by max possible amount.  Don't worry about finding exact highest bottleneck path.  Maintain scaling parameter .  Let Gf () be the subgraph of the residual graph consisting of only arcs with capacity at least . 110 s 4 2 t 1 170 102 122 Gf 110 s 4 2 t 170 102 122 Gf (100)Capacity Scaling Scaling-Max-Flow(G, s, t, c) { foreach e  E f(e) 0  smallest power of 2 greater than or equal to C Gf residual graph while (  1) { Gf() -residual graph while (there exists augmenting path P in Gf()) { f augment(f, c, P) // augment flow by   update Gf() }   / 2 } return f }Capacity Scaling: Correctness Assumption. All edge capacities are integers between 1 and C. Integrality invariant. All flow and residual capacity values are integral. Correctness. If the algorithm terminates, then f is a max flow. Pf.  By integrality invariant, when  = 1  Gf() = Gf.  Upon termination of  = 1 phase, there are no augmenting paths. Capacity Scaling: Running Time Lemma 1. The outer while loop repeats 1 + log2 C times. Pf. Initially C   < 2C.  decreases by a factor of 2 each iteration.  Lemma 2. Let f be the flow at the end of a -scaling phase. Then the value of the maximum flow f* is at most v(f) + m . (Sanity check: |v(f*) – v(f)|  m, and  shrinks, so v(f) converges towards v(f*) ) Lemma 3. There are at most 2m augmentations per scaling phase.  Let f be the flow at the end of the previous scaling phase.  Lemma 2 v(f*)  v(f) + m (2).  Each augmentation in a -phase increases v(f) by at least .  Theorem. The scaling max-flow algorithm finds a max flow in O(m log C) augmentations. It can be implemented to run in O(m2 log C) time.  proof on next slide (Why?)Capacity Scaling: Running Time Lemma 2. Let f be the flow at the end of a -scaling phase. Then value of the maximum flow is at most v(f) + m . Pf. (almost identical to proof of max-flow min-cut theorem)  We show that at the end of a -phase, there exists a cut (A, B) such that cap(A, B)  v(f) + m .  Choose A to be the set of nodes reachable from s in Gf().  By definition of A, s A.  By definition of f, t  A. So v(f*)-v(f)  cap(A,B) – v(f)  m original network s t A BBest Known Algorithms For Max Flow Reminder: The scaling max-flow algorithm runs in O(m2 log C) time. Currently there are algorithms that run in time • O(mn log n) • O(n3) • O(min(n2/3, m1/2) m log n log C) Active topic of research: • Flow algorithms for specific types of graphs • Special cases (bipartite matching, etc) • Multi-commodity flow •