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.


1 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.

  • $\begingroup$ If $s$ is the source vertex, what does it mean to add the edge $(v,s)$? What are the source and sink vertices in $G'$? I feel like I must be missing some detail here. $\endgroup$
    – D.W.
    Commented Feb 27, 2015 at 7:08
  • $\begingroup$ @D.W. - For any network $G,c,s,t$, consider the network $G',c',u,t$, where two vertices are added $u,v$ and the edges $u\to v, v\to s, v\to t$ are added as well, with capacity equal (or larger than) the max flow in $G,c,s,t$. Given a max flow for the new network $u\to v\to t$ with value $f^*$, if I reduce the capacity of $(v,t)$ to 0, this means you need to compute the flow in the reduced network (which is now equivalent to the original network) from scratch. It shows that if $O(VE)$ time is needed for computing flow in a graph, you'll need $O(VE)$ time to compute "reduced edge flow". $\endgroup$
    – R B
    Commented Feb 27, 2015 at 13:10
  • $\begingroup$ So $u$ is the source vertex of the new flow network (of $G'$) and $t$ is the sink vertex of the new flow network? OK, that makes sense now. $\endgroup$
    – D.W.
    Commented Feb 27, 2015 at 21:31
  • $\begingroup$ Great answer! Your example definitely clears up the worst case. However, I am still curious about methods that would perform well on average, or in practice. $\endgroup$
    – iheap
    Commented Feb 27, 2015 at 22:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.