How to find max flow in a graph after decrementing an edge capacity?

We're given a graph $G=(V, E)$, with source $s$ and sink $t$, $s\neq t$, and that all capacities are non-negative integers. Also the max flow itself is given, so we receive the value of max flow for each edge. We're also given some edge $e'$.

How can the max flow be found if we decrement the capacity value of an edge $e'$ by $1$ in linear time?

• – D.W.
Jan 23 '18 at 21:31

If the capacity of edge $$c(e') \ge f(e') + 1$$ i.e. the max flow remains the same, there is no chance max flow increase, as it would increased without decreasing $$c(e')$$.

Suppose that $$c(e') = f(e')$$ (this edge is saturated) and we decrease the capacity in $$1$$ unit. You need to remove one unit of flow from $$s$$ to $$t$$ that goes through edge $$e'$$. Let say that $$e'= (u,v)$$.

Removing flow: Just run two BFS, one starting from $$s$$ to $$u$$ going through edges that has flow greater that $$0$$, the other from $$v$$ to $$t$$ equally from edges that has flow greater than $$0$$. (It is guaranteed you will reach your goal in both cases since there is a unit of flow traversing this edge). Select a path from $$s$$ to $$u$$ and remove $$1$$ unit of flow from each edge and do the same with a path from $$v$$ to $$t$$. Complexity: $$O(|V| + |E|)$$

Recover max flow: Now we have a valid flow network but not necessarily the network with max flow. So now you just need to run one iteration of augmenting path with the capacity of edge $$e'$$ reduced. (Just like running one iteration of Ford-Fulkerson algorithm) Running just one iteration has the complexity of a single DFS which is $$O(|V| + |E|)$$.

Overall complexity of this approach would be $$O(|V| + |E|)$$ which is linear in the amount of nodes and edges.

• How do we know that only one iteration of Ford-Fulkerson will be enough?
– Yos
Jan 18 '18 at 17:45
• Because flow will augment in at most one unit. Jan 18 '18 at 17:45
• in the removing flow stage what if the edges adjacent to $u$ and/or $v$ have flow of exactly one?
– Yos
Jan 18 '18 at 17:48
• What would be the problem in that case? the flow in all in the path from $s-u$ and $v-t$ get decreased by $1$ unit. If it was exactly $1$ the new flow is $0$. Jan 18 '18 at 20:39
• @Addem actually this solution is $O(|E|)$ since you are only traversing the graph using dfs/bfs three times starting from a fixed node (you don't need to iterate over the nodes). Apr 10 '20 at 0:37