# Efficient recalculation of the maximum flow when edge capacities are reduced

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

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.

• 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. – D.W. Feb 27 '15 at 7:08
• @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". – R B Feb 27 '15 at 13:10
• 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. – D.W. Feb 27 '15 at 21:31
• 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. – iheap Feb 27 '15 at 22:08