Efficient recalculation of the maximum flow when edge capacities are reduced

Question

Assume that we have a (directed) graph $G(V \cup \{s, t\}, E)$ and an (integer) capacity function $c : E \mapsto \mathbb{N}$. Let $f : E \mapsto \mathbb{N}$ be a maximum $s-t$ flow on this graph. Suppose that some edge capacities are suddenly reduced; i.e. we now have to work with a capacity function $c_R : E \mapsto \mathbb{N}$ such that $c_R(e) \leq c(e)$ for all $e \in E$.

Can we efficiently "adjust" our old optimal flow $f$ to find the new optimal flow $f_R$ instead of recomputing the latter from scratch?

Note 1: Assume that the reduction is consequential; i.e. $c_R(e) < f(e)$ for at least one $e \in E$. Also, for the sake of simplicity, you can assume that the capacity is reduced for only one edge.

Note 2: One approach would be to treat the problem as an LP. In this case, capacity reductions will simply change variable bounds. Thus, we can use a warm-start capable LP solving method to get from $f$ to $f_R$. For example, if we used the dual simplex method (DSM), we can compute $f_R$ from $f$ via a (hopefully) small number of pivots, each of which involves $O(|V| \cdot |E|)$ arithmetic operations.

Note 3: This discussion tries to tackle the related (harder?) problem of adding/removing vertices and modifying the maximum flow.

Answer 1

In the worst case, even reduction of the capacity of a single edge may force you to recalculate the flow from scratch.

To see this, consider a flow network $(G,c,s,t)$, i.e., $G=(V,E)$ be a graph such that $s,t\in V$, $c:E\to\mathbb N$ is some capacity function, $s$ is a source vertex, and $t$ is a sink vertex.

Now define a new flow network $(G',c,u,t)$, as follows. $G'=(V\cup\{u,v\}, E\cup\{(u,v),(v,t), (v,s)\}$ is a new graph. The source vertex of the new flow network is $u$ and the sink vertex is $t$. Assume that $c((u,v))=c((v,s))=c((v,t))=f^*$, where $f^*$ is the value of the max flow in the original network.

Assume now that I give you a maximum flow $f'$ for $G'$ (from $u$ to $t$), namely, $f'((u,v))=f'((v,t))=f^*$ and $f'=0$ for all other edges. In other words, $f'$ pushes $f^*$ units of flow along the path $u \to v \to t$.

Now if we reduce $c(v,t)$ to 0, you have to compute the flow for the original network from scratch.