UC Berkeley—CS 170: Efficient Algorithms and Intractable Problems Handout 19Lecturer: David Wagner April 10, 2003Notes 19 for CS 1701 Network Flows1.1 The problemSuppose that we are given the network of Figure 1 (top), where the numbers indicatecapacities, that is, the amount of flow that can go through the edge in unit time. We wishto find the maximum amount of flow that can go through this network, from s to t.STACBD521212533STACBD5212125332STACBD521212533STACBD52121253322Figure 1: Max flow.This problem can also be reduced to linear programming. We have a nonnegativevariable for each edge, representing the flow through this edge. These variables are denotedfs,a, fs,b, . . . We have two kinds of constraints:• capacity constraints such as fs,a≤ 5 (a total of 9 such constraints, one for each edge),and• flow conservation constraints (one for each node except s and t), such as fa,d+ fb,d=fd,c+ fd,t(a total of 4 such constraints).Notes number 19 2We wish to maximize fs,a+ fs,b, the amount of flow that leaves s, subject to theseconstraints. It is easy to see that this linear program is equivalent to the max-flow problem.The simplex method would correctly solve it.In general, we are given a “network” that is just a directed graph G = (V, E) with twospecial vertices s, t, such that s has only outgoing edges and t has only incoming edges, anda capacity cu,vassociated to each edge (u, v) ∈ E. Then the maximum flow in the networkis the solution of the following linear program, having a variable fu,vfor every edge.maximizePv:(s,v)∈Efu,vsubject tofu,v≤ cu,vfor every (u, v) ∈ EPu:(u,v)∈Efu,v−Pw:(v,w)∈Efv,w= 0 for every v ∈ V − {s, t}fu,v≥ 0 for every (u, v) ∈ E1.2 The Ford-Fulkerson AlgorithmIf the simplex algorithm is applied to the linear program for the maximum flow problem, itwill find the optimal flow in the following way: start from a vertex of the polytope, such asthe vertex with fu,v= 0 for all edges (u, v) ∈ E, and then proceed to improve the solution(by moving along edges of the polytope from one polytope vertex to another) until we reachthe polytope vertex corresponding to the optimal flow.Let us now try to come up directly with an efficient algorithm for max flow based onthe idea of starting from an empty flow and progressively improving it.How can we find a small improvement in the flow? We can find a path from s to t (say,by depth-first search), and move flow along this path of total value equal to the minimumcapacity of an edge on the path (we can obviously do no better). This is the first iterationof our algorithm (see the bottom of Figure 1).How to continue? We can look for another path from s to t. Since this time we alreadypartially (or totally) use some of the edges, we should do depth-first search on the edgesthat have some residual capacity, above and beyond the flow they already carry. Thus, theedge (c, t) would be ignored, as if it were not there. The depth-first search would now findthe path s − a − d − t, and augment the flow by two more units, as shown in the top ofFigure 2.Next, we would again try to find a path from s to t. The path is now s − b − d − t (theedges c − t and a − d are full are are therefore ignored), and we augment the flow as shownin the bottom of Figure 2.Next we would again try to find a path. But since edges a − d, c − t, and s − b arefull, they must be ignored, and therefore depth-first search would fail to find a path, aftermarking the nodes s, a, c as reachable from S. We then return the flow shown, of value 6,as maximum.There is a complication that we have swept under the rug so far: When we do depth-firstsearch looking for a path, we use not only the edges that are not completely full, but wemust also traverse in the opposite direction all edges that already have some non-zero flow.This would have the effect of cancelling some flow; cancelling may be necessary to achieveoptimality, see Figure 1.2. In this figure the only way to augment the current flow is via theNotes number 19 3STACBD521212533STACBD5212125334STACBD521212533STACBD5212125334222422222minimum cutwith capacity2+2+2=6maximum flow of value 64Figure 2: Max flow (continued).Notes number 19 4path s − b − a − t, which traverses the edge a − b in the reverse direction (a legal traversal,since a − b is carrying non-zero flow).111111S TAB11Flows may have to be cancelled.The algorithm that we just outlined is the Ford-Fulkerson algorithm for the maximumflow problem. The pseudocode for Ford-Fulkerson is as follows.1. Given in input G = (V, E), vertices s, t, and capacities cu,v. Initialize fu,vto zero forall edges.2. Use depth-first search to find a path from s to t. If no path is found, return thecurrent flow.3. Let c be the smallest capacity along the path.4. For each edge (u, v) in the path, decrease cu,vby c, increase fu,vby c, and increasecv,uby c (if the edge (v, u) does not exist in G, create it). Delete edges with capacityzero.5. Go to step 21.3 Analysis of the Ford-Fulkerson AlgorithmHow can we be sure that the flow found by the Ford-Fulkerson algorithm is optimal?Let us say that a set of vertices S ⊆ V is a cut in a network if s ∈ S and t 6∈ S. Let usdefine the capacity of a cut to bePu∈S,v6∈S,(u,v)∈Ecu,v.We first note that if we fix a flow f , and consider a cut S in the network, then theamount of flow that passes “through” the cut, is independent of S, and it is, indeed, thecost of the flow.Lemma 1Fix a flow f. For every cut S the quantityXu∈S,v6∈S,(u,v)∈Ef(u, v) −Xu∈S,v6∈S,(v,u)∈Ef(v, u)is always the same, independently of S.Notes number 19 5As a special case, we have thatPuf(s, u) =Pvf(v, t), so that the flow coming out ofs is exactly the flow getting into t.Proof: Assume fu,vis defined for every pair (u, v) and fu,v= 0 if (u, v) 6∈ E.Xu∈S,v6∈Sfu,v−Xu6∈S,v∈Sfu,v=Xu∈S,v∈Vfu,v−Xu∈S,v∈Sfu,v−Xu6∈S,v∈Sfu,v=Xu∈S,v∈Vfu,v−Xu∈V,v∈Sfu,v=Xv∈Vf(s, v) +Xu∈S−{s},v∈Vfu,v−Xu∈V,v∈S−{s}fu,v=Xv∈Vfs,vand the last term is independent of S. 2A consequence of the previous result is that for every cut S and every flow f , the costof the flow has to be smaller than or equal to the capacity of S. This is true because thecost of f isXu∈S,v6∈Sfu,v−Xv6∈S,u∈Sfv,u≤Xu∈S,v6∈Sfu,v≤Xu∈S,v6∈Scu,vand the right-hand side is exactly the capacity of S. Notice how this implies that if we finda cut S and a flow f such that the cost of f