Question

Let G = (V, E) be a flow network with source s, sink t, and integer capacities. Suppose that we are given a maximum flow in G. (a) Suppose that the capacity of a single edge (u, v) ∈ E is increased by 1. Give an O(V + E)-time algorithm to update the maximum flow. (b) Suppose that the capacity of a single edge (u, v) ∈ E is decreased by 1. Give an O(V + E)-time algorithm to update the maximum flow.

Answer 1

Answer and explanation:

a) Just executive one iteration of the ford —Fulkerson algorithm. The edge (u, v) in E with increased capacity ensures that the edge (u,v) is in the residual graph. So look for an augmenting path and update the flow if a path is found. Time: 0 (V + E) = 0(E) if we find the augmenting path with either depth — first or breadth — first search.

To see that only one iteration is needed, consider separately the cases in which (u,v) is or is not an edge that crosses a minimum cut, then increasing its capacity does not change the capacity of any minimum cut. And hence the values of the maximum flow does not change. If (u,v)does cross a minimum cut, then increasing its capacity by 1 increases the capacity of that minimum cut by 1, and hence possibly the value of the maximum flow by 1. In this case, there is either no augmenting path, or the augmenting path increases flow by 1. No matter what, one iteration of ford —Fulkerson suffices.  

b) Let f be the maximum flow before reducing C(u,v).

If f (u,v) = 0, we don't need to do anything.

If f (u,v)> 0, we will need to update the maximum flow assume from now on that f (u,v) > 0, which in turn implies that f (u,v) $\ge$ 1  

Define f' (x,y) = f (x,y) for all x,y ∈ V , except that f f(u,v) = f (u,v) - 1, although f' obeys all capacity constraints even after C(u,v) has been reduced. It is not a legal flow as it violates skew symmetry and flow conservation at u and v. f ' has one more unit of flow entering u then leaving u, and it has on more unit of flow leaving v than entering v. The idea is to try to reroute this unit of flow so that it goes out of u and into v via some other path. If that is not possible, we must reduce the flow from s to u and from v to t by one unit.  

Look for an augmenting path from u to v.If there is such a path, augment the flow along that path. If there is no such path reduce the flow from s to u by augmenting the flow from u to s. That is, find an augmenting path it and augment. The flow along that path similarly, reduce the flow from v to t by finding an augmenting path I and augmenting the flow along that path.  

Time: 0 (V + E) = O(E) if we find the paths with either DFS or BFS.