15.082J and 6.855J and ESD.78J October 19, 2010Max Flows 3Preflow-Push Algorithms2Review of Augmenting PathsAt each iteration: maintain a flow x.Let G(x) be the residual network.At each iteration, find a path from s to t in G(x).In the shortest augmenting path algorithm, we kept distance labels d( ), and we sent flow along the shortest path in G(x).This lecture: present and analyze a different type of max flow algorithm called preflow-push. New analysis technique: potential functions.3Flows vs. PreflowsAugmenting Path AlgorithmFlow into i = Flow out of iPush flow along a path from s to td(j) = distance from j to t in the residual network. Preflow AlgorithmFlow into i ≥ Flow out of i for i ≠ s.Push flow in one arc at a timed(j) ≤ distance from j to t in the residual network d(t) = 0 d(i) ≤ d(j) + 1 for each arc (i, j) ∈ G(x),4PreflowsAt each intermediate stages we permit more flow arriving at nodes than leaving (except for s)A preflow is a function x: A → R s.t. 0 ≤ x ≤ u and such that e(i) = ∑j∈Nxji- ∑j∈Nxij≥ 0, for all i ∈ N – {s, t}.i.e., e(i) = excess at i = net excess flow into node i.The excess is required to be nonnegative.5A Feasible PreflowThe excess e(j) at each node j ≠ s, t is the flow in minus the flow out.s342 5t333222212100Note: total excess = flow out of s minus flow into t.6Distance LabelsDistance labels d( ) are valid for G(x) ifi. d(t) = 0ii. d(i) ≤ d(j) + 1 for each (i, j) ∈ G(x)Defn. An arc (i, j) is admissible if rij> 0 and d(i) = d(j) + 1. Lemma. Let d( ) be a valid distance label. Then d(i) is a lower bound on the distance from i to t in the residual network.i tP = the shortest path from i to t in G(x)d( )01234 237Distance labels and gapsWe say that there is a gap at a distance level k (0 < k < n) if there is no node with distance label k.Lemma. Suppose there is a gap at distance level k. Then for any node j with d(j) > k, there is no path from j to t in the residual network.Proof. The shortest path from j to t would have to pass through a node whose distance level is k.i tP = the shortest path from i to t in G(x)d( )01234 238Active nodes in the residual networkA node j in G\{s} is active if:• e(j) > 0 and • there is no gap at a distance level less than d(j)The preflow push algorithm will push flow from active nodes “towards the sink”, relying on d( ).6312 10210427stkd( ) = kw e( ) = w9Push/Relabel, the fundamental subroutineSuppose we have selected an active node i.Procedure Push/Relabel(i)beginif the network contains an admissible arc (i, j) thenpush  : = min{ e(i), rij } units of flow from i to j;else replace d(i) by min{d(j) + 1 : (i, j) ∈ A(i) and rij> 0}end;10Pushing using current arcsTail Head Res. Cap Admissible? 4 1 0 No 4 2 1 No 4 3 4 Yes 4 5 0 No 4 6 2 Yes Suppose that node 4 is active, and has excess.341 235613222e(4) = 2Scan arcs in A(4) one at a time using “Current Arc” till an admissible arc is found.Push on (4,3)Pushing on (4,3)11Tail Head Res. Cap Admissible? 4 1 0 No 4 2 1 No 4 3 4 Yes 4 5 0 No 4 6 2 Yes 341 235613222e(4) = 2Push on (4,3)e(3) = 1Send min (e(4), r43) = 2units of flow.2e(4) = 0 e(3) = 3For the next push from node 4, start with arc (4,3).Update the residual capacities and excesses.12Goldberg-Tarjan Preflow Push AlgorithmProcedure Preprocessx :=0;compute the exact distance labels d(i) for each node;xsj:= usjfor each arc (s, j) ∈ A(s); d(s) := n;Preflow Push AnimationAlgorithm PREFLOW-PUSH;preprocess;while there is an active node i do select an active node i;push/relabel(i);convert the max preflow into a max flowNote: the “while loop” ends when there are no active nodes; i.e., if e(j) > 0, then d(j) is above a gap.13Preview of Results on Goldberg-Tarjan Preflow PushThe GT algorithm is superb both in theory and in practice.Suppose that the flow into t is v* after the “while loop.”We will show the following: 1. Distance labels stay valid after a push and after a relabel. They never go down in a relabel.2. It is possible to convert the preflow into an s-t flow with a feasible flow out of s (and into t) equal to v*.3. The algorithm determines a cut with  the algorithm determines a preflow with max flow into t  the algorithm determines a minimum s-t cut4. The running time of the algorithm is O(n2m)14Distance labels remain valid0kk-1 1tijSuppose that we push flow in (i, j) when d(i) = k and d(j) = k - 1.Validity remains satisfied for all arcs of G(x). And it is also satisfied for arc (j, i). That is, d(j) ≤ d(i) + 1 = k+1.Let x be the flow before the push.Let x’ be the flow after the push.There is at most one arc in G(x’) that is not in G(x), and that arc is (j, i)Before a relabel of node i, the distance labels are valid, but no arc out of i is admissible. So, in a relabel of node i, d(i) must increase.15Converting any preflow into a flowLet x’ be any preflow at some stage of the algorithm.Express x’ using flow decomposition.s322 1t210234106454024242-15Note: s is the only node with deficit.FlowPaths-4 2s-3-2-1 2s-3 1s-4-1-t 4s-2-t 4s-3-t 2The feasible flow is the sum of the flows on paths from s to t.The flow into t is the same for the flow and preflow.16Finding the minimum cut Let d*( ) be the distance labels at the end of the algorithm.  Let k* be the minimum positive value such that there is a gap at level k*.  Let S* = {j : d*(j) < k*}. Let T* = {j : d(j*) > k*}.Theorem. (S*, T*) is a minimum capacity cut, and the capacity of the cut is the amount of flow into t.17The minimum cutThere is no arc (i, j) from S* to T* in G(x*) because for each arc (i, j) ∈ G(x*) d(i) ≤ d(j) + 1.• If i ∈ S* and j ∈ T*, then x*ij= uij• If i ∈ T* and j ∈ S*, then x*ij= 0There is no excess at a node of T* because the algorithm terminated.0k*+1k*k*-121tsnn+1S*T*ije(j) = 0The flow v* into t is v* = CAP(S*, T*) because any flow across the cut must go to t. (Same as in proof of max-flow min-cut).18Something happened to the actors in the first English play in America. What was it?They were arrested. Acting was considered evil.What was the first country to give women the vote?New Zealand, in 1890.The first phone book ever issued was in New Haven, CT. How many names were in the book?50. It was published in 1878.Mental Break19In London, in the 1700s, one could purchase insurance for a particularly catastrophic event. But it was not clear how one could prove …