algorithmmathnetwork-flow

Network Flow Update Values


I am practicing Algorithms problems from my book and came across this one:

You are given a directed network G with n nodes and m edges, a source s, a sink t and a maximum flow f from s to t. Assuming that the capacity of every edge is a positive integer, describe an O(m + n) time algorithm for updating the flow f in each of the following two cases.

(i) The capacity of edge e increases by 1.

(ii) The capacity of edge e decreases by 1.

It seems like it would be as simple as walking through the network flow edges and adjusting flows, but I do not think it is really that simple. Wikipedia only give algorithms that are O(n^2 m) or O(n m^2). Any help or thoughts would be appreciated.


Solution

  • There is a solution here.

    Suppose e is an edge between u and v.

    Increased capacity

    The idea for increasing the capacity is to simply do a DFS in the residual flow graph for a path from s to t.

    Decreased capacity

    If the edge is unsed in the maximum flow then you are done.

    Otherwise, the idea is to see if there is an alternative path from u to v in the residual flow graph. This takes O(n+m). If found, then you can increase the maximum flow by 1.

    Otherwise, you need to decrease the flow. You do this by finding a path from u to s along which the flow can increase by 1, and a path from t to v along which the flow can increase by 1. (The increases are in a reverse direction so this reduces the flow from s to t).