COS 521 A Riff* on the Goldberg-Rao Maximum Flow AlgorithmFall 2009TarjanThese notes describe a version of the Goldberg-Rao maximum flow algorithm and a proof of itstime bound, along with a discussion of how it differs from the original algorithm.The algorithm assumes integer arc capacities. It maintains a flow f and a real value.D The latteris used to classify the residual arcs: a residual arc is large, medium, or small if its residualcapacity is at least 2 ,D at least delta but less than 2 ,D or less than ,D respectively. Each archas a length, which is zero if is large, one if it is medium or small, or � if it is not residual.Given the arc lengths, the distance ( )d vof a vertex v is the length of a shortest path from v to t.The algorithm begins with f equal to the zero flow and D equal to the smallest power of twogreater than the maximum arc capacity. Then it computes ( )d vfor every vertex v. Finally, itrepeats the following step until ( )d s =�(there is no augmenting path):General Step: If 2/3 1/2( ) min{ , },d s n ml> = replace delta by / 2Dand recompute ( )d vfor everyvertex v. Otherwise, proceed as follows. Let G� be the network induced by the set of residualarcs {( , ) ( ) ( ) or ( ) ( )v w d v d w d v d w> =and( , )v wis not small}, with each arc having a capacityequal to the minimum of its residual capacity and delta. Form G�� from G�by contracting eachstrong component in G�to a single vertex whose capacity is equal to delta. Find a blockingflow f�� on G .�� Extend f�� to a flow f' on G� by routing flow through each strong component.Add f' to f. Recompute d for every vertex v. Lemma 1. There are at most lg 3U + distinct values of D during the running of the algorithm.Proof. The initial value of D is at most lg 1.U + Once 1/ 2,D=all residual arcs are large,because the algorithm maintains flow integrality. Thus ( )d sremains equal to 0, and D remainsequal to 1/2, until ( )d s =� and the algorithm stops. WLemma 2. Each iteration of the general step either halves D, or increases the value of f by atleast D without changing ( ),d sor increases ( )d sby at least one.Proof. Consider an iteration of the general step that does not change D. Let l and ,l� and dand ,d� be the length functions before and after the step, and the distance functions before andafter the step, respectively. We claim that ( ) ( , ) ( )d v l v w d w�� + for any arc ( , )v w (1)1The definition of d implies that ( ) ( , ) ( ).d v l v w d w� + Thus (1) holds unless ( , ) ( . ).l v w l v w�<But this can happen only if ( , )w vis in G ,� which implies ( ) ( ),d v d w� from which (1) followsby the non-negativity of .l�Since ( ) 0,d t =(1) implies by induction on the number of arcs on the shortest length l�- pathfrom v to t that ( ) ( ).d v d v�� In particular, ( ) ( ).d s d s��Now suppose the step increases the value of f by less than D. Then f��saturates at least onearc on each path from s to t in G ,�� which implies that f� saturates at least one arc on each pathfrom s to t in G ;� that is, f�is blocking on G .� To complete the proof of the lemma, we need toshow that ( ) ( ).d s d s�> This is immediate if ( ) .d s�=� Suppose not. Consider a shortestlength l�- path G from s to t. Because f� is blocking on G, this path contains at least one arc( , )x y not in G .� We shall show ( ) ( , ) ( )d x l x y d y�< +(2)It must be the case that ( ) ( );d x d y� otherwise ( , )x y would be in G .� If ( ) ( ),d x d y<(2) holds.Suppose ( ) ( ).d x d y= Then (2) holds unless ( , ) 0;l x y�= that is, ( , )x y is large after the step.But this implies that ( , )x y is medium or large before the step, since the step increases ( , )f y xby at most D. Then ( , )x y is in G ,� a contradiction. Thus (2) holds.Combining (2) with inequality (1) for the other arcs on Ggives ( ) ( ).d s d s�< WLemma 3. The number of iterations of the general step is O( log ).UlProof. Before D is halved for the first time, all arcs are small, ,G G�� �= and the argument in the proof of Lemma 2 implies that every iteration of the general step increases ( )d sby at least one. The number of times ( )d s can increase between changes of D is at most 2.l + We shall show that between changes of D the number of times f can increase without ( )d s changing is at most 2 .l The lemma then follows from Lemma 1.Each change of f without an increase in ( )d s happens after the first change in D. Consider thestate just before a change in D. The change occurs because ( ) .d s l> Each positive integer( )k d s� defines a canonical cut whose source side is { ( ) }.v d v k� Any residual arc crossing acanonical cut must be small, and a small arc can cross at most one canonical cut. Suppose1/2.ml = Since there are at least l canonical cuts, at least one has no more than /m l residualarcs crossing it. Such a cut has a residual capacity of at most / .m l lD = D Suppose on theother hand that 2/3.nl = There must be a value of k such that the number of vertices v with( )d vequal to k or 1k - is at most 2 / .n l The number of arcs crossing the canonical cutdefined by k is at most 2( / ) ;n l l= hence the residual capacity of the cut is at most .l D2We conclude that in either case there is a cut whose residual capacity is at most ;l D hence theflow value can increase by at most .l D This means that after D is halved once but before it ishalved twice, the number of steps that can change f without increasing ( )d s is at most 2 .l WTheorem 1. With appropriate implementations of the various parts of the algorithm, the runningtime of the algorithm is 2O( mlog(n / m)log U).lProof. Computing ( )d v for every vertex v takes O( )mtime by a modified backward breadth-first search that preferentially traverses arcs of zero …