Network flows

Important algorithms of network flows with example.

1. NETWORK FLOWS By- Richa Bandlas(1913106)

2. Contents : What is Network Flow? Maximum Flow problem and Ford-Fulkerson Algorithm Max-Flow and Min-cut Choosing Good Augmenting paths Preflow -Push Maximum-flow algorithm Bipartite Matching Problem

3. Flow Networks: A flow network is a connected, directed graph G = (V, E),which is simple path. Each edge e has a non-negative, integer capacity c(e). • A single source s ∈ V. • A single sink t ∈ V. • No edge enters the source and no edge leaves the sink. Flow capacity

4. FLOW Def. An s-t flow is a function f : E → R that assigns a real number to each edge. f (e) is the amount of material carried on the edge e. Constraints on f : 0 ≤ f (e) ≤ c(e) for each edge e. (capacity constraints) For each node v except s and t, we have: = (balance constraints: whatever flows in, must flow out). The value of a flow f , denoted ν(f ) , is defined to be the amount of flow generated at the source :  

5. Maximum Flow Problem Given a flow network, find a flow of maximum possible value. Start with Greedy Approach: Suppose we let f (e) = 0 for all edges (no flow anywhere). Choose some s − t path (P) and find its minimum capacity. Push flow on this path. Repeat.

6. PATH Bottleneck s->a->t 5 s->b->d->t 8 s->c->t 5 Now we are stuck . So Flow = (5+8+5 = 18) but is this Maximum flow?

7. Residual Graph: We define a residual graph G` . G` depends on some flow f : G` contains the same nodes as G. Forward edges : For each edge e = (u, v) of G for which f (e) < c(e) , include an edge e = (u, v) in G` with capacity c(e)− f (e) (Also called Residual capacity). Backward edges: For each edge e = (u, v) in G with f (e) > 0, we include an edge e = (v, u) in G` with capacity f (e). Residual Graph G` of previous graph is: Blue edges- Residual capacity Black edges- Backward edges showing flow which can be reverted

8. Augmenting Path: Let P be an s − t path in the residual graph G`. Let bottleneck(P, f ) be the smallest capacity in G` 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 Following function yields a new flow f` in G:. 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

9. After f`= augment(P, f ), we still have a flow: Consider the path s->a->d->b->c->t in residual graph G`: Bottleneck = 3 Original Graph Residual Graph after applying flow MAX-FLOW = 5+8+5+3= 21

10. Ford-Fulkerson Algorithm Max-Flow Initially f (e) = 0 for all e in G //Initialize While there is an s-t path in the residual graph Gf Let P be a simple s-t path in Gf f` = augment(f , P) Update f to be f` Update the residual graph Gf to be Gf` Endwhile Return f

11. Capacity constraints : Let e be an edge on P: if e is forward edge, it has capacity c(e) − f (e). Therefore, f`(e) = f(e) + bottleneck(P, f ) ≤ f(e) + (c(e) − f (e)) ≤ c(e) 2. if e is a backward edge, it has capacity f (e). Therefore, c(e)>= f(e) >= f`(e) = f(e) − bottleneck(P, f ) ≥ f(e) − f (e) = 0 TERMINATION CONDITION: At every step, the flow values f (e) are integers. At every step we increase the amount of flow v(f ) sent by at least 1 unit. We can never send more than C=  

12. Running Time: If G has m edges, G` has ≤ 2m edges. Can find an s − t path in G` in time O(m + n) time with DFS or BFS. Since m ≥ n/2 (every node is adjacent to some edge), O(m + n) = O(m). (This is for one iteration)

13. Flows and Cuts We will show that the flow that is returned by the Ford-Fulkerson Algorithm has the maximum possible value of any flow in G. Cut: Given a network G, define a cut (also called an s-t cut) to be a partition of the vertex set into two disjoint subsets A V and B = V \ A, where s A and t . Capacity: The capacity(A, B) of an s-t cut (A, B) is the sum of the capacities of edges leaving . C(A,B) = Flow: Let f be any s-t flow, and (A, B) any s-t cut. Then ν(f ) =  

14. THEOREM: Proof: This shows that value of every flow is upper-bounded by capacity of every cut.

15. MAX FLOW /MIN CUT ALGORITHM: Let f` be the flow returned by our algorithm. Look at G` but define a cut in G. Let (A`,B`) be the cut in G, where A`=[ s,a ] and B`= [ b,d,c,t ].

16. Edges (u, v) from A` to B` must be saturated — otherwise there would be a forward edge (u, v) in G` and v would be part of A`. Edges (v, u) from B` to A` must be empty — otherwise there would be a backedge (u, v) in G` and v would be part of A`. Fig ref: Jon Kleinberg Given a flow f of maximum value, we can compute an s-t cut of minimum capacity in O(m) time, A` B` 5 3 8 5 = 21

17. Good Augmenting Paths Worst case of choosing augmenting path can be if it increases the flow by 1 unit in each iteration. If we try to augmenting path based on maximum bottleneck value, then it will be time consuming. Capacity Scaling: Maintain a scaling parameter, , and look for paths which have bottleneck capacity of at least . Conditions on : is power of 2. < = maximum capacity out of s It works on residual graph and using DFS, selects the path with bottleneck at least . Similar to Ford-Fulkerson Algorithm.  

18. Example Step1 : Finding maximum capacity: u = max(10,8,5) => u = 10 Step2 : choose = power of 2 <= u. So, Step3 : With =8  

19. With = 4   With   Path Bottleneck S->b->d->t 8 8 S->c->t 5 4 S->a->t 5 4 S->a->d->b->c->t 3 2 Path Bottleneck S->b->d->t 8 8 S->c->t 5 4 S->a->t 5 4 S->a->d->b->c->t 3 2

20. Final residual graph: With =1 : There is no path available.   With =0 : There is no path available. So, Algorithm Terminates   Flow = 8+5+5+3 =21

21. Algorithm: Algorithm taken from Jon Kleinberg

22. Given a flow f of um value, we can compute an s-t cut of minimum capacity in O(m) time, The number of iterations of the outer While loop is at most 1+ log 2 C. The number of augmentations in a scaling phase is at most 2 m. . The Scaling Max-Flow Algorithm in a graph with m edges and integer capacities finds a maximum flow in at most 2 m( 1+ log 2 C) augmentations. It can be implemented to run in at most O(m 2 log 2 C) time.

23. Preflow -Push Maximum-Flow Algorithm Performs local updates repeatedly until global constraint is satisfied. Algorithm is based on two assumptions: Doesn’t obey flow conservation. T he flow entering the node is allowed to be more than the flow leaving it. This is termed as Preflow . “Height” is assigned to each node in the graph called labels(h(v)) and flow is only sent from higher label to lower label. Increasing height of a node is called “Relabel” operation. In the beginning “Source” is the highest point . “Sink” and all other nodes are at the lowest point.

24. Constraints: Now heights and and a preflow is compatible only if: For all edges (v , w) in the residual graph, we have h(v) ≤ h(w) + 1. Edges must respect the capacity condition. Active node: A node is active if there is some excess flow coming out of it. Excess Flow: A preflow where all nodes other than s and t have zero excess is a flow.

25. Algorithm Steps: Step1 : Initialize source h(s)=n and all other nodes with h(v)=0 and e(v)=0. Step2 : s sends flow to its neighbors, completely saturating all its outgoing edges. Above step make neighbors nodes as active. Step3 : We increase the height of the “active” node with a “Relabel” operation If h is the minimum height among neighbors that can accept flow Then height is relabeled to (h+1). Step4 : Algorithm terminates when there are no “active” nodes left.

26. Step 1: Relabel a with h=1 and push 5 on ( a,t ) With h=1, push 3 on edge ( a,d ) Thirdly, Relabel a with h=7, and push (-2) on edge ( a,s )

27. Step 2: Relabel ‘b’ with h=1 , push 8 on edge (b,d) Relabel ‘c’ with h=1 , push 5 on edge (c,t)

28. Step 3: Relabel ‘d’ with h=1, push 8 on edge (d,t) Relabel ‘d’ with h=2, push (-3) on edge (c,b)

29. Step 4: relabel ‘b’ with h=2, push 3 on edge ( b,c )

30. Step 5: As ‘c’ has height, h=1, which is already greater than ‘t’ which has h=0 , so we can push 3 on edge ( c,t ). As we can see, all the vertices has excess flow e=0, so the algorithm terminates here. Maximum Flow = 21

31. Running time: Running time of Preflow -Push Relabel Algorithm is O(V 2 . E), where V is Vertices and E is edges. Note: This can be further improved by using advanced techniques.

32. Maximum Bipartite Matching Bipartitie Graph: A bipartite graph (or bigraph ) is a graph whose vertices can be divided into two disjoint and independent sets U and V such that every edge connects a vertex in U to one in V. Suppose we have { a,b,c,d,e } as People and {1,2,3,4,5} as tasks. Each person can do only some of the jobs. A matching gives an assignment of people to tasks. Maximum matching: one that contains as many edges as possible (we want to get as many tasks done as possible).

33. We need to find out , Maximum Bipartite Matching in a given Biparitite Graph. Use of Network Flow: Transform a Bipartite Graph into Network flow, Finding the maximum flow , will give maximum bipartite Matching. STEPS TO TRANSFORM BIPARTITE GRAPH INTO NETWORK FLOW: Given bipartite graph G = (A ∪ B, E), direct the edges from A to B. Add new vertices s and t. Add an edge from s to every vertex in A. Add an edge from every vertex in B to t. Make all the capacities 1. Solve maximum network flow problem on this new graph G` Edges used in maximum network flow is the largest possible matching.

34. People Jobs

35. Analysis As capacities are integers, flow will be integral. Each edge has capacity of 1, so it is either included in flow or not. Let M be the edges going from people to tasks. M is a matching: For M being a matching, no two edges share an end point. We can choose at most one edge leaving any node in People. We can choose at most one edge entering any node in Jobs. People Jobs

36. M is maximum matching If there is a matching of k edges, there is a flow f of value k. We find the maximum flow f. This corresponds to a matching M of k edges. If there were a matching with > k edges, we would have found a flow with value > k, contradicting that f was maximum. Hence, M is maximum.

37. Running Time Running time of ford Fulkerson algorithm is O( mC ) where m is the number of edges and C is the capacity. Here, C=|People|=|Jobs|= n ,that is, number of nodes So, Running time of Bipartite matching is O( mn ).

38. References: Algorithm Design by Jon Kleinberg, Eva Tardos (section 7.1 to 7.5) https://www.cs.cmu.edu/~avrim/451f13/lectures/lect1010.pdf

39. Thank you!!