Network Flow Problems - Stanford University

1 Network Flow ProblemsJaehyun ParkCS 97 SIStanford UniversityJune 29, 2015 OutlineNetwork Flow ProblemsFord-Fulkerson AlgorithmBipartite MatchingMin- cost Max-flow AlgorithmNetwork Flow Problems2 Network Flow Problem A type of Network optimization problem Arise in many different contexts (CS 261): Networks: routing as many packets as possible on a givennetwork Transportation: sending as many trucks as possible, whereroads have limits on the number of trucks per unit time Bridges: destroying (?!) some bridges to disconnectsfromt,while minimizing the cost of destroying the bridgesNetwork Flow Problems3 Network Flow Problem Settings: Given a directed graphG= (V, E), where each edgeeis associated with its capacityc(e)>0. Two special nodessourcesand sinktare given(s6=t) Problem: Maximize the total amount of flow fromstotsubject to two constraints Flow on edgeedoesn t exceedc(e) For every nodev6=s, t, incoming flow is equal to outgoing flowNetwork Flow Problems4 Network Flow Example (from CLRS) Capacities Maximum flow (of 23 total units) Network Flow Problems5 Alternate Formulation: minimum Cut We want to remove some edges from the graph such thatafter removing the edges, there is no path fromstot The cost of removingeis equal to its capacityc(e) The minimum cut problem is to find a cut with minimumtotal cost Theorem:(maximum flow) = ( minimum cut) Take CS 261 if you want to see the proofNetwork Flow Problems6 minimum Cut Example Capacities minimum Cut (red edges are removed) Network Flow Problems7 Flow Decomposition Any valid flow can be decomposed into flow paths andcirculations s a b t: 11 s c a b t.

2 1 s c d b t: 7 s c d t: 4 Network Flow Problems8 OutlineNetwork Flow ProblemsFord-Fulkerson AlgorithmBipartite MatchingMin- cost Max-flow AlgorithmFord-Fulkerson Algorithm9 Ford-Fulkerson Algorithm A simple and practical max-flow algorithm Main idea: find valid flow paths until there is none left, andadd them up How do we know if this gives a maximum flow? Proof sketch: Suppose not. Take a maximum flowf and subtract our flowf. It is a valid flow of positive total the flow decomposition, it can be decomposed into flowpaths and circulations. These flow paths must have beenfound by Ford-Fulkerson. Algorithm10 Back Edges We don t need to maintain the amount of flow on each edgebut work with capacity values directly Iffamount of flow goes throughu v, then: Decreasec(u v)byf Increasec(v u)byf Why do we need to do this? Sending flow to both directions is equivalent to canceling flowFord-Fulkerson Algorithm11 Ford-Fulkerson Pseudocode Setftotal= 0 Repeat until there is no path fromstot: Run DFS fromsto find a flow path tot Letfbe the minimum capacity value on the path Addftoftotal For each edgeu von the path: Decreasec(u v)byf Increasec(v u)byfFord-Fulkerson Algorithm12 Analysis Assumption: capacities are integer-valued Finding a flow path takes (n+m)time We send at least 1 unit of flow through the path If the max-flow isf , the time complexity isO((n+m)f ) Bad in that it depends on the output of the algorithm Nonetheless, easy to code and works well in practiceFord-Fulkerson Algorithm13 Computing Min-Cut We know that max-flow is equal to min-cut And we now know how to find the max-flow Question: how do we find the min-cut?

3 Answer: use the residual graphFord-Fulkerson Algorithm14 Computing Min-Cut Subtract the max-flow from the original graphFord-Fulkerson Algorithm15 Computing Min-Cut Mark all nodes reachable froms Call the set of reachable nodesA Now separate these nodes from the others Cut edges going fromAtoV AFord-Fulkerson Algorithm16 Computing Min-Cut Look at the original graph and find the cut: Why isn tb ccut?Ford-Fulkerson Algorithm17 OutlineNetwork Flow ProblemsFord-Fulkerson AlgorithmBipartite MatchingMin- cost Max-flow AlgorithmBipartite Matching18 Bipartite Matching Settings: nstudents andddorms Each student wants to live in one of the dorms of his choice Each dorm can accommodate at most one student (?!) Fine, we will fix this Problem: find an assignment that maximizes the number ofstudents who get a housingBipartite Matching19 Flow Network Construction Add source and sink Make edges between students and dorms All the edge weights are 1 Bipartite Matching20 Flow Network Construction Find the max-flow Find the optimal assignment from the chosen edgesBipartite Matching21 Related Problems A more reasonable variant of the previous problem.

4 Dormjcan accommodatecjstudents Make an edge with capacitycjfrom dormjto the sink Decomposing a DAG into nonintersecting paths Split each vertexvintovleftandvright For each edgeu vin the DAG, make an edge fromulefttovright And many Matching22 OutlineNetwork Flow ProblemsFord-Fulkerson AlgorithmBipartite MatchingMin- cost Max-flow AlgorithmMin- cost Max-flow Algorithm23 Min- cost Max-Flow A variant of the max-flow problem Each edgeehas capacityc(e)and costcost(e) You have to paycost(e)amount of money per unit flowflowing throughe Problem: find the maximum flow that has the minimum totalcost A lot harder than the regular max-flow But there is an easy algorithm that works for small graphsMin- cost Max-flow Algorithm24 Simple (?) Min- cost Max-Flow Forget about the costs and just find a max-flow Repeat: Take the residual graph Find a negative- cost cycle using Bellman-Ford If there is none, finish Circulate flow through the cycle to decrease the total cost ,until one of the edges is saturated The total amount of flow doesn t change!

5 Time complexity: very slowMin- cost Max-flow Algorithm25 Notes on Max-Flow Problems Remember different formulations of the max-flow problem Again,(maximum flow) = ( minimum cut)! Often the crucial part is to construct the flow Network We didn t cover fast max-flow algorithms Refer to the Stanford Team notebook for efficient flowalgorithmsMin- cost Max-flow Algorithm26