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. – Marcelo Fornet 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$. – Marcelo Fornet Jan 18 '18 at 20:39
• @Yos I make a mistake, I didn't mean greater than 1, but greater than 0 (greater or equal than 1) – Marcelo Fornet Jan 18 '18 at 23:42