Question

et NV,E] be a capacitated directed network with unique fixed source and unique fixed sink, no edges into the source, and no edges out of the sink. To eadh vertex u,e V, assign a number μj equal to 0 or-1. To each edge (Unuj)e E, assign a number yy defined by yy -max (0, H, - Hj). (See the discussion immediately preceding Example 10.) a. Prove that-t +pj + yi,2 0 for all i and j. b. Prove that yy is equal to 0 or 1 for all i and j. c. Prove that at least one optimal solution of (3) takes the form described above. Hint: Use the max-flow min-cut theorem.]

Answer 1

Suppose that we have a max flow f for the network N, and that we are told that a particular edge (u, v) is having its capacity increased by 1. First observe that this increase cannot *decrease* the max flow of the network - clearly every flow in the original network is a flow in the modified network. The increase in (u, v)’s capacity may or may not *increase* the max flow. Let N0 be the modified network (same as N except (u, v) has capacity c(u, v) + 1). Consider the flow f in the network N0 , and let N0 f be the residual network. I claim that f is a max flow in N0 if and only if there is *no* augmenting path in N0 f . Hence we have the following algorithm to update the max flow when the capacity of an edge is increased by 1: 1. Take the original max flow f and compute N0 f. 2. Search for an augmenting path in N0 f . 3. If we find an augmenting path p, return f + fp as the max flow for the update network. OTHERWISE if we find no augmenting path, return f. The algorithm is correct for the following reasons. First if there is no augmenting path in N0 f , then by Corollary 14 of lecture slides 13-14, f is a max flow. Second, if there is an augmenting path p in N0 f , then (i) The capacity c(p) of p in N0 f is 1 (if it was greater than this, f could not have been a max flow for N). (ii) Define f 0 = f + fp. Then N0 f 0 has no augmenting path (same reason as for (i)). Hence in the case where N0 f does have an augmenting path p, we know that f 0 = f+fp is a max flow of N.

This algorithm can be executed in the time it takes to construct the residual network O(|V| + |E|), and the time it takes to find one augmenting path (O(|V| + |E|) by breadth-first search). Hence it is O(|V| + |E|) in total.

If we decrease the value of (u, v) by 1 from its original value in N, then the max flow of the updated network N0 can be no greater than the max flow of N (and possibly less). If it is the case that the max flow f of N satisfies f(u, v) < c(u, v), then f will also be a flow (and hence the max flow) in N0 (where (u, v) has capacity c(u, v) − 1). However, if we had f(u, v) = c(u, v) in N, then the max flow of N0 might have value strictly less than |f|. Here is our algorithm. 1. If we had f(u, v) < c(u, v) in N, then f is a (max) flow in N0 . Return f. 2. OTHERWISE (if we had f(u, v) = c(u, v)). (i). Find a simple path p1 in Nf from u to s. (ii). Find a simple path p2 in Nf from t to v. (iii). Take the path p2,(v, u), p1 in Nf, and route 1 unit of flow from t to s along this path. Adding this to f, we get a new flow f 0 of value |f|−1 in N, with f 0 (u, v) < c(u, v). Hence f 0 is a flow in N0 also. (iv) Finally perform a search in N0 f 0 for an augmenting path. (v) If we find an augmenting path p in N0 f 0, return the flow f 0 + fp (of value |f|). (vi) Otherwise, return f 0 . Note that a residual network only keeps edges with strictly +ve value (nb for (iii)). The running time of the algorithm is O(|V| + |E|) (same reason as for (a) except we may do 3 breadth-first searches, in (i), (ii), (iv), here).