I am working on a project where I need to be able to compute the maximum flow between two nodes in a graph after one of the edge weights has been incremented or decremented by 1. The graph is directed and edge weights are all integers. I can find the maximum flow the first time, by Ford-Fulkerson's algorithm or some variant, but at each step thereafter it would be great if I could use a different (faster) algorithm to find the max flow. At each step, only one of the edge weights is changed, and it is only changed by a value of +1 or -1. What sort of algorithm could do this incremental update for me? It needs to be faster than recomputing the max flow from scratch. It could also be two separate algorithms (but similar I would hope): one for the incrementing case and one for the decrementing case. Thanks in advance for the help!
-
1$\begingroup$ cs.stackexchange.com/q/86801/755, cs.stackexchange.com/q/12703/755 $\endgroup$– D.W. ♦Commented Jan 23, 2018 at 21:31
1 Answer
You can do it in $\small \mathcal{O}(m + n)$ time where $\small m$ and $\small n$ are the # of edges and vertices respectively. Let the edge to be updated be $\small e = (u, v)$.
If you increment the capacity of $\small e$ by $\small 1$, the maximum flow increments by at most $\small 1$. Hence, starting with the current max flow $\small f$, you only need to find an augmenting path in the residual graph one more time, which costs $\small \mathcal{O}(m + n)$ time. Recall that each augmentation increments the flow value by at least $\small 1$. Therefore, it is guaranteed after the augmentation (if any), the flow attained is maximum.
If you decrement the capacity of $\small e$ by $\small 1$, the maximum flow decrements by at most $\small 1$. If the new capacity (after decreased by $\small 1$) $\small c(e) \geq f(e)$, where $\small f(e)$ is the current flow value of $\small e$, then nothing need to be conducted. Otherwise, we have to decrease the flow value of $\small e$. Let $\small s \rightarrow u$ be a simple path from $\small s$ to $\small u$, in which all edges have positive flow values and similarly define $\small v \rightarrow t$. We then decrease the flow values by $\small 1$ for all edges in the path $\small s \rightarrow u \rightarrow v \rightarrow t$. Finally, we again search for an augmenting path in the resultant residual graph.
