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?

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.

StackExchange Computer Science Q#86801, answer score: 13