Advanced Network Flow Applications in Optimization
[30] Choose a number r larger than any |bi|, and say that the scaled benefit bi0 of keeping application i on the old system is bi0=r, while the scaled benefit of moving it is bi1=r+bi. So our problem is equivalent to that of finding a partition of the applications that maximizes the sum of the scaled benefits minus the sum of pij for all pairs i and j that are split. Define a directed graph G=(V,E) with nodes s,t,v1,v2,..,vn, edges (s,vi),(vi,s) of capacity bi0,(t,vi),(vi,t) of capacity bi1, and (vi,vj),(vj,vi) of capacity pij. Let B=SUMi (bi0+bi1). Now, the capacity of an s-t cut (X, Y) can be written as c(X,Y)= SUM(i!EX)bi0 + SUM(i!EY)bi1 + SUM(iEX,jEY)pij = B- SUM(iEX)bi0 – SUM(iEY)bi1 + SUM(iEX,jEY)pij.
Thus, finding a cut of minimum capacity is the same as maximizing the objective function in the previous paragraph.
[31] This is a complete parallel to the airline scheduling problem in the text. The boxes are like the flights, and where we previously encoded the idea that one crew can perform flight i followed by flight j, we analogously encode the idea that box i can be nested inside box j. More precisely we reduce the given problem to a max flow problem where units of flow correspond to sets of boxes nested inside one visible box. We construct the following graph G: • For each box i, G has two nodes ui and vi and an edge between them that corresponds to this box. This edge (ui,vi) has a lower bound of 1 and a capacity of 1. (Each box is exactly in one set of boxes nested one in another.) • For each i and j so that box j nests inside box i, there is an edge (vi, uj). (One can store box j inside i.) • G also has a source node s (corresponding to the back room where boxes are stored) and a sink node t (corresponding to nothing inside empty boxes). • For each i, G has an edge (s, ui) with a lower bound of 0 and a capacity of 1. (Any box can be visible.) • For each j, G has an edge (vj, t) with a lower bound of 0 and a capacity of 1. (Any box can be empty.) We claim the following: (1) There is a nesting arrangement with k visible boxes if and only of there is a feasible circulation in G with demand —k in the source node s and demand k in the sink t. Proof. First, suppose there is a nesting arrangement with k visible boxes. Each sequence of nested boxes inside one visible box i1,i2,..,in defines a path from s to t: (s,ui1,vi1,ui2,vi2,..Uin,vin,t). Therefore we have k paths from s to t. The circulation corresponding to all these paths satisfy all demands, capacity and lower bound. Conversely, consider a feasible circulation in our network. Without lost of generality, assume that this circulation has integer flow values. There are exactly k edges going to t that carries one unit of flow. Consider one of such edges (vi, t). We know that (ui, vi) has one unit of flow. Therefore, there is a unique edge into ui that carries one unit of flow. If this edge is of the kind (vj, ui) then put box i inside j and continue with box j. If this edge of the kind (s,ui), then put the box i in the back room. This box became visible. Continuing in this way we pack all boxes into k visible ones. So we can answer the question whether there is a nesting arrangement with exactly k visible boxes. Now to find the min possible number of visible boxes we answer this question for k=1,2,3.. So on till we find a positive answer. The max number of this iteration is n, thus the algo is polynomial since we can find a feasible circulation in polynomial time.
[32] This is true. To prove this, suppose that for some graph G, and nodes x, y, and z, we had x–G,k–>y and y–G,k–>z, but x–G,k–>z did not hold. This means that there is an x-z cut (A, B) such that fewer than k edges cross from A to B. Now we ask which set contains node y. If y E A, then this contradicts the existence of k edge-disjoint paths from y to z; and if y E B, then this contradicts the existence of k edge-disjoint paths from x to y.
[33] If we put a capacity of 1 on each edge, then by the integrality theorem for maximum flows, there exist k edge-disjoint x-y paths iff there exists a flow of value k. By the max-flow min-cut theorem, this latter condition holds if and only if there is no x-y cut (A, B) of capacity less than k. Now suppose there were a y-x cut (B’,A’) of capacity strictly less than k, and consider the x-y cut (A’,B’). We claim that the capacity of (A’,B’) is equal to the capacity of (B’,A’). For if we let 6-(v) /* DELTA MINUS*/ and 6+(v) denote the number of edges into and out of a node v respectively, then we have c(A’,B’) — c(B’,A’) = |{(u,v):uEA’, vEB’}| – |{(u,v):uEB’, vEA’}| = |{(u,v):uEA’, vEB’}| + |{(u,v):uEA’, vEA’}| – |{(u,v):uEA’, vEA’}| + |{(u,v):uEB’, vEA’}| = SUMvEA 6+(v) – SUMvEA 6-(v) =0. It follows that c(A’, B’) < k=”” as=”” well,=”” contradicting=”” our=”” observation=”” in=”” the=”” first=”” paragraph.=”” thus,=”” every=”” y-x=”” cut=”” has=”” capacity=”” at=”” least=”” k,=”” and=”” so=”” there=”” exist=”” k=”” edge-disjoint=”” y-x=”” paths.=””>
[34] (a) The algorithm is based on the following flow network G. There is a single source s and a single sink t. For each device i, we have two nodes ui and vi, and there is also an edge (s, ui) with capacity k and an edge (vi, t) with capacity b. If devices i and j (i!=j) are within d meters to each other, we will have two edges (ui, vj) and (uj, vi), each of which has capacity 1. We then compute a max-flow f on G. If all the edges leaving s are saturated, then it is possible to make the back-up system. If fui,vj=1, then device j is in the back-up set of device i. The time complexity is also dominated by a max-flow computation. For each device i, it has two roles: a device that needs back-up, which is represented by node ui, and a device that offers back-up service, which is represented by node vi. The capacity of (vi, t) gives the maximum ability of device i to serve as a back-up node. The way we set up (ui, vj) correctly abstracts the condition when a device can serve as a back-up of another one, and also prevents counting twice of a same device in any back-up set. So if (s, ui) is saturated for any device i, its back-up set will contains exactly k other devices. (b) This part is similar to the previous one, but the back-up set of a device is no longer as simple. For any device i, we have k sets: X1^i,X2^i,..Xk^i. Xt^i={j|f(di j) >= pt ^ j != i} /*NOTATIONS, 2nd is union; di j= dij where i is subscript*/ where di j is the distance between devices i and j. The back-up set of i should contain one device from each set Xt^i. However,Xt^i E Xt+1^i, so we must avoid choosing the same device in i’s back-up set for more than once. We set up a flow network as follows. There is a single source s and a single sink t. For each device i, we have a node vi, and k other nodes ui1,ui2,..Uik, and each edge (s,uit) has capacity 1 and edge (vi, t) has capacity b. We also have n2 — n other nodes wij (i!=j). From each wij, there is an edge (wij, vj) with capacity 1. If j E Xt^i, there will be an edge (uit, wij) with capacity 1. We will also compute a max-flow f for that flow network. If all the edges leaving s are saturated, we will answer “yes”, and if (wij, vj) is saturated, j is in i’s back-up set.
[35] To make sure that a selected pixel v will be in the foreground we consider the same network as in the chapter, but we increase the capacity on the edge (s, v) to 5d + 1. Note that this is greater than the total capacity of all edges outgoing from v (at most four edges to neighbor pixels, plus the edge to t). So the minimum cut will now definitely has v on the source side (otherwise we could move v to source side and decrease the capacity of the cut). Therefore the following algorithm works. Compute a maximum flow f and find a mini-mum cut, as in the chapter. Then, for each pixel v selected by the user, we want to raise the capacity on the edge (s, v) to 5d+ 1. To do so we increase the capacity of this edge 5d+ 1— a times by 1 each time (where a is the old capacity). Each time we will use algorithm from Solved Exercise 1 to compute a new maximum flow in O(m+n) time. Then we compute a minimum cut in O(m) time. The overall time per mouse-click is (5d+ 1)O(m+n) + O(m) = O(d(m+n)). Since each non-source node in our graph has at most 5 outgoing edges and s has n outgoing edges, the total number of edges in the graph is m <= 5n+=”” n=”O(n).” therefore=”” o(d(m+m))=”0(dn).”>=>
[36] First, consider a cut (A0, B0), where Ao is just {s}. Note, that there no edges with capacity L going out s, therefore the capacity of the cut (A0, B0) does not depend on L. Let L be greater than this capacity. Then any cut cutting an edge of capacity L has capacity at least L. So such cut can not be a minimum cut, because it has larger capacity than (A0, B0) cut. Now consider a minimum cut (A, B). Let i be an arbitrary pixel. If vi,k E A for some k then is also in A, since there is an edge (vi,k, vi,k-i) with capacity L and no edge with capacity L is out of A. Let f(i) is the maximum number such that vi,f(i) E A (such number exists because vi,0 = s E A). Then A contains all nodes vi,k where k <= f(i),=”” and=”” a=”” contains=”” all=”” nodes=”” vi,k=”” where=”” k=””> f (i). This number f(i) will represent the label of the pixel i (i.E. We put i in Ak when f(i) = k). So any labeling of the pixels corresponds to a cut (A, B) where A = {(vi,k |k <= label=”” of=”” i}.=”” we=”” have=”” just=”” proved=”” that=”” any=”” minimum=”” cut=”” corresponds=”” to=”” some=”” labeling.=”” up=”” to=”” now=”” the=”” capacity=”” of=”” such=”” cut=”” is =”” sum(k=”0″ to=”” m)=”” ai,f(i)=”” -=”” sum(k=”0″ to=”” m)=”” sum(i:f(i)=”k)” ai,k =”” which=”” is=”” equal=”” to=”” the=”” first=”” term=”” of=”” our=”” cost=”” function.=”” so=”” the=”” main=”” issue=”” remaining=”” is=”” to=”” encode=”” the=”” separation=”” costs.=”” if=”” pixels=”” i=”” and=”” j=”” are=”” neighbors,=”” we=”” join=”” vi,k=”” and=”” vj,k,=”” for=”” each=”” k,=”” by=”” two=”” edges=”” in=”” both=”” directions=”” of=”” capacity=”” pi,j.=”” consequently,=”” (a,=”” b)=”” cuts=”” the=”” edges=”” of=”” the=”” kind=”” (vi,k,=”” vj,k)=”” when=”” vi,k=”” e=”” a=”” and=”” vj,k=”” e=”” b,=”” i.E.,=”” when=”” k=””>=><= f(i)=”” and=”” k=””> f(j). For any pair of neighbors i and j if f(j) >= f(i) then there are exactly f(j) — f(i) such k that f(i) <= k=””>=>< f(j).=”” therefore=”” there=”” are=”” f(j)=”” —=”” f(i)=”” edges=”” out=”” of=”” a.=”” the=”” overall=”” capacity=”” of=”” these=”” edges=”” is=”” (f(j)=”” —=”” f(i))pi,j=”” which=”” is=”” exactly=”” the=”” desired=”” separation=”” cost.=”” so=”” we=”” have=”” proved=”” that=”” the=”” cost=”” of=”” any=”” labeling=”” is=”” equal=”” to=”” capacity=”” of=”” the=”” corresponding=”” cut.=”” hence,=”” the=”” minimum=”” cost=”” labeling=”” corresponds=”” to=”” the=”” minimum=”” cut.=””>
[37] We transform an instance with this kind of negativity property to an equivalent one where all capacities are non-negative. Consider any node v, and suppose there are edges (s, v) , (v, t) . In fact if one of these edges does not exist, then we simply add it with capacity 0; this makes for an equivalent problem. (One could do without this but it makes the following description simpler.) If both capacities on these edges are non-negative, we leave them as is. Otherwise, we add dv= min(|csv| , |cvt|) /*sv n vt are subscript*/ to both capacities. Now all capacities are non-negative, and we compute a minimum cut (A, B) as usual. We claim that (A, B) is a minimum cut in the original network as well. Consider the difference between the capacity of (A, B) in the original network (which we’ll denote c(A, B)) and the capacity in the new network (which we’ll denote c'(A, B)). For each node v for which the capacities of incident edges were modified, the capacity of the cut (A, B) has been changed by exactly dv, regardless of which side of the cut v is on. Thus, letting D = SUMv dv, we have c'(A, B) = c(A, B) + D. Since D is independent of the choice of (A, B), this says that finding a cut minimizing c(A, B) is the same as finding one minimizing c'(A, B).
[38] We approach this using the technique from the airline scheduling application. We can imagine the various prefixes as being like “flights,” that must be done, and a single permu-tation can potentially handle two different prefixes if one if a subset of another. Thus, we build the following flow network. The node set of the underlying graph G is defined as follows. • For each set Si, G will have the two nodes ui and vi. • G will also have a distinct source node s and sink node t.
The edge set of G is defined as follows. • For each i, there is an edge (ui, vi) with a lower bound of 1 and a capacity of 1. (Each set on the list must be a prefix of some permutation.) • For each i and j so that Si C Si /*belongs: C with a line under it*/, there is an edge (vi, uj) with a lower bound of 0 and a capacity of 1. (The same permutation can have both Si and Sj as a prefix.) • For each i, there is an edge (s, ui) with a lower bound of 0 and a capacity of 1. (Any permutation can begin with set Si.) • For each j, there is an edge (vj, t) with a lower bound of 0 and a capacity of 1. (Any permutation can end with set Sj.) • There is an edge (s, t) with lower bound 0 and capacity l. (We don’t need to use all l permutations.)
Finally, the node s will have a demand of —l, and the node t will have a demand of l. All other nodes will have a demand of 0. Now, suppose there is a set of l’ < l=”” permutations=”” that=”” collectively=”” contain=”” all=”” the=”” given=”” sets=”” as=”” prefixes.=”” then=”” for=”” each=”” permutation,=”” we=”” can=”” define=”” one=”” unit=”” of=”” flow=”” to=”” go=”” through=”” the=”” sets=”” that=”” it=”” contains=”” as=”” prefixes,=”” in=”” order=”” of=”” increasing=”” set=”” size.=”” the=”” remaining=”” l=”” —=”” l’=”” units=”” of=”” flow=”” can=”” go=”” directly=”” from=”” s=”” to=”” t.=”” this=”” gives=”” a=”” feasible=”” circulation.=”” conversely,=”” suppose=”” there=”” is=”” a=”” feasible=”” circulation.=”” then=”” there=”” is=”” one=”” with=”” integer=”” values,=”” and=”” using=”” the=”” technique=”” from=”” the=”” airline=”” scheduling=”” application,=”” we=”” can=”” “follow”=”” individual=”” units=”” of=”” flow=”” from=”” s=”” to=”” t=”” so=”” as=”” to=”” construct=”” l’=”” many=”” s-t=”” paths=”” that=”” collectively=”” pass=”” through=”” all=”” edges=”” of=”” the=”” form=”” (ui,=”” vi).=”” we=”” now=”” map=”” each=”” such=”” path=”” p=”” to=”” a=”” single=”” permutation.=”” if=”” p=”” passes=”” through=”” sets=”” si1,..,sir,=”” then=”” by=”” the=”” construction=”” of=”” the=”” flow=”” network=”” we=”” have=”” si1=”” c_=”” c=”” with=”” underscore:=”” belongs=”” to*/=”” si2=”” c_=”” sir,=”” so=”” we=”” can=”” define=”” a=”” permutation=”” that=”” begins=”” with=”” the=”” columns=”” in=”” si1,=”” in=”” any=”” order,=”” followed=”” by=”” the=”” columns=”” in=”” si2,=”” —=”” si1,=”” in=”” any=”” order,=”” and=”” so=”” forth,=”” ending=”” with=”” columns=”” not=”” in=”” sir.=”” the=”” set=”” of=”” permutations=”” defined=”” this=”” way=”” satisfies=”” the=”” requirements=”” of=”” the=”” problem.=””>
[39] We’ll discuss three different solutions for this problem. The first two are based on flows, the third is not based on anything from this chapter. We use the following notation. Assume the matrix given is (n+ 1) by (m + 1) and let A be the matrix of the first m rows and first n columns. Let csi /*i is subscript*/ denote the sum of entries in column i of A, and rsj denote the sum of entries in row j of A. By assumption rsi and csj are integer. Let SUM= SUMi rsi = SUMj csj be the sum of all the matrix entries. (a) We define a maximum flow problem as follows. There will be nodes s and t, a node ri corresponding to each row i of A, and a node cj corresponding to each column j of A. There will be edges (s, ri) of capacity rsi and edges (cj, t) of capacity csj. Now we add edges of capacity 1 for each (ri, cj) pair such that aij > 0. To solve part (a) we run a maximum flow algorithm. The capacity of the edges out of s limits the maximum flow value to at most SUM. Note that the rounding exists iff the maximum flow value in the above network is SUM. Fact. Roundings of matrix A are in one-one correspondence with integer flows f of value SUM in the network defined above. The correspondence is defined by rounding aij up iff f(ri, cj) = 1. (b) For each entry aij let bij = [aiji] /*lowerbound*/ and a’ij = aij — bij. Let A’ and B denote the matrices with these entries. Then A = A’+B, all entries of A’ satisfy 0 <= a’ij=””>=>< 0,=”” all=”” row=”” and=”” column=”” sums=”” of=”” a’=”” are=”” integer,=”” and=”” roundings=”” of=”” a’=”” are=”” in=”” one-to-one=”” correspondence=”” of=”” roundings=”” of=”” a.=”” so=”” we=”” can=”” use=”” the=”” solution=”” for=”” part=”” (a)=”” for=”” the=”” matrix=”” a’=”” and=”” obtain=”” a=”” solution=”” for=”” (b). =”” (c)=”” the=”” easiest=”” way=”” to=”” see=”” part=”” (c)=”” is=”” to=”” use=”” the=”” fact=”” that=”” f(ri,=”” cj)=”” -=”” aij=”” defines=”” a=”” feasible=”” flow=”” of=”” value=”” sum=”” in=”” the=”” network=”” defined=”” in=”” (a),=”” and=”” hence=”” the=”” maximum=”” flow=”” value=”” is=”” sum,=”” and=”” we=”” know=”” that=”” a=”” flow=”” network=”” with=”” integer=”” capacities=”” has=”” an=”” integer=”” maximum=”” flow.=”” so=”” there=”” is=”” an=”” integer=”” flow=”” of=”” value=”” sum.=””>
[40] We test whether e’ = (u, v) could enter the MST as follows. We first lower the cost of e’ by E (epsilon) and raise the cost of all other edges by E (epsilon). We then form a graph G’ by deleting all edges whose cost is greater than or equal to that of e’. Finally, we determine whether the minimum u-v cut in G has at most k edges. If the answer is “yes,” then by raising the cost of these k edges to oo (infinity), we see that e’ is one of the cheapest edges crossing a u-v cut, and so it belongs to an MST. Conversely, suppose e’ can be made to enter the MST. Then this remains true if we continue to lower the cost of e’ by as much as possible, and if we continue to raise the costs of all other edges by as much as possible. Now at this point, consider the set E’ of k edges whose costs we need to alter arbitrarily. If we delete E’ from the graph, then there cannot be a u-v path consisting entirely of edges lighter than e’; thus, there is no u-v path in the graph G’ defined above, and so E’ defines a u-v cut of value at most k.
[41] Let a* be the earliest arrival time of any job, and d* the latest deadline of any job. We break up the interval I = [a*, d*] at each value of any aj, dj, ti, or t’i. Let the resulting sub-intervals of I be denoted I1,12,..,Ir, with Ii = [si, s’i]. Note that s’i = si+i in our notation; we let qi — s’i — si denote the length of interval Ii in time steps. Observe that the set of processors available is constant throughout each interval Li; let ni denote the size of this set. Also the set of jobs that have been released but are not yet due is constant throughout each interval I. We now construct a flow network G that tells us, for each job j and each interval Ii, how much time should be spent processing job j during interval Ii. From this, we can construct the schedule. We define a node uj for each job j, and a node vi for each interval Ii. If Ii C_ [aj, di], then we add an edge (uj, vi) of capacity qi. We define an edge from the source s to each uj with capacity lj, and define an edge from each vi to the sink t with capacity niqi. Now, suppose there is a schedule that allows each job to complete by its deadline, and suppose it processes job j for zji units of time in the interval Ii. Then we define a flow with value lj on the edge (s, uj), value zji on the edge (uj, vi), and sufficient flow on the edge (vi, t) to satisfy conservation. Note that the capacity of (vi, t) cannot be exceeded, since we have a valid schedule. Conversely, given an integer flow of value SUMj lj in G, we run job j for zji – f(uj,vi) units of time during interval Ii. Since the flow has value SUMj lj, it clearly saturates each edge (s, uj), and so uj will be processed for lj units of time as required, if we can guarantee that all jobs j can really be scheduled for zji units of time during interval Ii. The issue here is the following: we are told that job j must receive zji units of processing time during h, and it can move from one processor to another during the interval, but we need to avoid having two processors working on the same job at the same point in time. Here is a way to assign jobs to processors that avoids this. Let P1,P2,..,Pn denote the processors, and let yj = SUM(r)><= niqi,=”” each=”” job=”” gets=”” a=”” sufficient=”” number=”” of=”” steps=”” allocated=”” to=”” it;=”” and=”” since=”” zji=””>=><= qi=”” for=”” each=”” j,=”” this=”” allocation=”” scheme=”” does=”” not=”” involve=”” two=”” processors=”” working=”” on=”” the=”” same=”” job=”” at=”” the=”” same=”” point=”” in=”” time.=””>=>
[42] (a) First define a flow f that satisfies the lower bound l on the edges. To do this, we can find a cycle or s-t path through each edge e with a non-zero lower bound, and increase the flow along the path or cycle to satisfy the lower bound. Note that if an edge e = (v, w) has a positive lower bound and no s-t path or cycle goes through e, then no flow can satisfy the lower bound. Now the idea will be to decrease the value of the flow f we obtained, while still satisfying the lower-bounds. To this end, we will define a flow problem with source t and sink s and a graph G’ on the set of nodes V. The graph G’ is the residual graph of f in G (except for the choice of the source and sink): Consider an edge e=(v,w) E E. If f(v,w) = l(v, w) than we add an edge to G’ with capacity oo (infinity). If f(v, w) > l(v, w) then we add two edges: edge (v, w) with capacity oo and the backwards edge (w, v) with capacity f (v, w) — l(v, w). Fact. A flow g is a maximum st flow in G’ iff f+g is a flow of minimum value in G. To see this claim note that feasible flows f’ in G are in one-to-one correspondence with flows g – f — f’ in G’, where a negative flow value g(v, w) < 0=”” is=”” understood=”” as=”” a=”” flow=”” of=”” value=”” |g(v,=”” w)|=”” on=”” the=”” opposite=”” edge(w,v).=”” further,=”” the=”” value=”” v(g)=”” is=”” v(f)=”” —=”” v(f’),=”” so=”” g=”” is=”” of=”” maximum=”” value,=”” ifff’=”” is=”” of=”” minimum=”” value. =”” (b)=”” to=”” get=”” an=”” analogous=”” min-flow=”” max-cut=”” theorem,=”” we=”” define=”” an=”” s-t=”” cut=”” as=”” follows:=”” we=”” will=”” call=”” an=”” s-t=”” cut=”” (a,=”” b)=”” feasible,=”” no=”” edge=”” goes=”” from=”” b=”” to=”” a.=”” we=”” say=”” that=”” the=”” lower-capacity=”” of=”” this=”” cut=”” is=”” the=”” sum=”” of=”” the=”” lower=”” bounds=”” on=”” its=”” edges=”” l(a,=”” b)=”SUM(e=(v,w)” out=”” of=”” a)=”” l(v,=”” w).=”” we=”” claim=”” that=”” the=”” maximum=”” capacity=”” l(a,=”” b)=”” of=”” a=”” feasible=”” cut=”” (a,=”” b)=”” equals=”” the=”” minimum=”” value=”” of=”” a=”” flow=”” f=”” satisfying=”” the=”” lower-bounds.=”” to=”” prove=”” this,=”” first=”” note=”” that=”” v(f)=””>= l(A, B) for all feasible cuts (A, B): v(f) = SUM(e=(v,w) out of A) f(v,w) – SUM(e=(v,w) into A) f(v,w) = SUM(e=(v,w) out of A) f(v,w) >= SUM(e=(v,w) out of A) l(v,w), where the equation follows as in a feasible cut no edges enter A. To see the other direction, let f be a flow of minimum value, and let Gf be its residual graph. Let A be the set of nodes that have a path to s in the residual graph. We will show that the cut (A, B) with B = V — A is a feasible cut with l(A, B) = v(f) which proves the claim. First note that l !E A (and hence (A,B) is a cut), as if there is a l-s path P in the residual graph, then pushing flow along this path will decrease the flow value, and f is of minimum value. Next we argue that the cut (A, B) is a feasible cut. Assume (A, B) is not a feasible cut: that is, there is an edge e = (v, w) entering A. There is a path P in the residual graph from w to s by the assumption that w E A. Edge (v, w) has no upper bound, so it is in the residual graph of any flow, and hence edge (v, w), and the path P form a path in the residual graph from v to s contradicting the assumption that v E B. The same argument also shows that all edges e=(v,w) leaving A must have f(v,w) = l(v,w). Using this fact, we get v(f)= SUM(e=(v,w) out of A) f(v,w) – SUM(e=(v,w) into A) f(v,w) = SUM(e=(v,w) out of A) f(v,w) = SUM(e=(v,w) out of A) l(v,w), which establishes the claim.
[43] This can be solved as an instance of the Project Selection Problem, since selecting a node v for the set implies that we must also select any node u with an edge to it. One difficulty is that the Project Selection Problem requires that we have a irected acyclic graph, while our flow network G here might have cycles. We could modify the algorithm and analysis of Project Selection to handle this, but we can also transform G so it is acyclic, as follows. Observe that for any strong component of G, either all nodes go into S or none do. Thus, we can create a super-node vx representing each strong component X, with dvX = SUM(vEX) dv. We then have an edge from vx to vy if some node in strong component X has an edge to some node in strong component Y. We’ll call this graph H. Now, the original problem is equivalent to finding a subset of H with no entering edges. Note that H is acyclic, since if it contained a cycle then all the super-nodes on this cycle would really be one big strong component, contradicting our assumption that each was a strong component on its own. There’s one more minor issue in mapping this onto Project Selection: in Project Selection we want a set with no edge leaving it, while here we want a set with no edges entering it. To handle this, we simply construct Hrev, by reversing all edges in H. Solving the Project Selection Problem on Hrev, and then “unpacking” the super-nodes representing strong components back into their constituent nodes in G, gives us the set S that we want.
=>=>