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.
There is a solution here.
Suppose e is an edge between u and v.
The idea for increasing the capacity is to simply do a DFS in the residual flow graph for a path from s to t.
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).