CMSC 451 Network Flows Slides By Carl Kingsford Department of Computer Science University of Maryland College Park Based on Sections 7 1 7 2 of Algorithm Design by Kleinberg Tardos Network Flows Our 4th major algorithm design technique greedy divide and conquer and dynamic programming are the others A little different than the others we ll see an algorithm for one problem and minor variants that is so useful that we can apply to to many practical problems Called network flow Network flow problem e g Suppose you want to ship natural gas from Alaska to Texas 2 10 5 There are pipes each with a capacity 7 8 How can you send as much gas as possible 3 3 1 7 3 8 4 12 10 10 Flow Network A flow network is a connected directed graph G V E Each edge e has a non negative integer capacity ce A single source s V A single sink t V No edge enters the source and no edge leaves the sink u x 20 20 30 s 10 30 10 t 10 v 10 w Assumptions To repeat we make these assumptions about the network 1 Capacities are integers 2 Every node has one edge adjacent to it 3 No edge enters the source and no edge leaves the sink These assumptions can all be removed Flow Def An s t flow is a function f E R 0 that assigns a real number to each edge Intuitively f e is the amount of material carried on the edge e u 10 30 10 30 20 10 10 15 20 20 s x 15 v 5 5 t 10 w 5 Flow constraints Constraints on f 1 0 f e ce for each edge e 2 For each node v except s and t we have X X f e f e e into v capacity constraints e leaving v balance constraints whatever flows in must flow out 3 4 v 10 7 2 Notation The value of flow f is X v f f e e out of s This is the amount of material that s is able to send out Notation f in v P f out v e into v P f e e leaving v f e Balance constraints becomes f in v f out v for all v 6 s t Maximum Flow Problem Definition Value The value v f of a flow f is f out s That is it is the amount of material that leaves s Maximum Flow Problem Given a flow network G find a flow f of maximum possible value A Greedy Start A Greedy Start 1 Suppose we let f e 0 for all edges no flow anywhere 2 Choose some s t path and push flow along it up to the capacities Repeat 3 When we get stuck we can erase some flow along certain edges How do we make this more precise Example u u 10 20 20 20 30 s 10 10 20 20 t 20 20 20 30 s 10 t 10 20 20 v v After 1 path we ve allocated 20 units Want to send the blue path Residual Graph We define a residual graph Gf Gf depends on some flow f 1 Gf contains the same nodes as G 2 Forward edges For each edge e u v of G for which f e ce include an edge e 0 u v in Gf with capacity ce f e 3 Backward edges For each edge e u v in G with f e 0 we include an edge e 0 v u in Gf with capacity f e Residual Graph e g If f e ce add edge e to Gf with capacity ce f e remaining capacity left If f u v 0 add reverse edge v u with capacity f e can erase up to f e capacity u u 10 20 20 20 30 s 10 20 t 20 s t 10 10 20 20 10 20 v v With Flow f Residual Graph Gf Augmenting Paths Let P be an s t path in the residual graph Gf Let bottleneck P f be the smallest capacity in Gf on any edge of P If bottleneck P f 0 then we can increase the flow by sending bottleneck P f along the path P Augmenting Paths 2 If bottleneck P f 0 then we can increase the flow by sending bottleneck P f along the path P augment f P b bottleneck P f For each edge u v P If e u v is a forward edge Increase f e in G by b add some flow Else e v u Decrease f e in G by b erase some flow EndIf EndFor Return f Ford Fulkerson Algorithm MaxFlow G initialize Set f e 0 for all e in G while there is an s t path in Gf While P FindPath s t Residual G f None f augment f P UpdateResidual G f EndWhile Return f After augment we still have a flow After f 0 augment P f we still have a flow Capacity constraints Let e be an edge on P if e is forward edge it has capacity ce f e Therefore f 0 e f e bottleneck P f f e ce f e ce if e is a backward edge it has capacity f e Therefore f 0 e f e bottleneck P f f e f e 0 Still have flow 2 Balance constraints An s t path in Gf corresponds to some set of edges in G s b b b b b In other pictures f P 6 f P 3 tt bo ck ne ttle v 7 10 6 v bo 7 10 b ot tle ne f P ck e len n tle ot b 3 k ec ck P f t Running Time 1 At every step the flow values f e are integers 2 At every step we increase the amount of flow v f sent by at least 1 unit 3 We can never send more than C P e leaving s ce Theorem The Ford Fulkerson algorithm terminates in C iterations of the While loop Running Time 1 At every step the flow values f e are integers Start with ints and always add or subtract ints 2 At every step we increase the amount of flow v f sent by at least 1 unit 3 We can never send more than C P e leaving s ce Theorem The Ford Fulkerson algorithm terminates in C iterations of the While loop Time in the While loop 1 If G has m edges Gf has 2m edges 2 Can find an s t path in Gf in time O m n time with DFS or BFS 3 Since m n 2 every node is adjacent to some edge O m n O m Theorem The Ford Fulkerson algorithm runs in O mC time Caveats etc Note this is pseudo polynomial because it depends on the size of the integers in the …