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

<p>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.</p>

<p>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.</p>

<p>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$.</p>

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

CC BY-SA 3.0
2015-02-27T07:08:51.993Z
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.
CC BY-SA 3.0
2015-02-27T13:10:32.510Z
@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
CC BY-SA 3.0
2015-02-27T21:31:22.477Z
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.
CC BY-SA 3.0
2015-02-27T22:08:13.527Z
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
CC BY-SA 3.0
2015-02-25T19:03:13.400Z
2015-02-27T21:34:08.267Z
2015-02-27T21:34:08.267Z
R B
<p>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$.</p>

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

<p><em>Note 1:</em> Assume that the reduction is consequential; i.e. $c_R(e) &lt; 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.</p>

<p><em>Note 2:</em> 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.</p>

<p><em>Note 3:</em> This <a href="https://cstheory.stackexchange.com/questions/9938/incremental-maximum-flow-in-dynamic-graphs">discussion</a> tries to tackle the related (harder?) problem of adding/removing vertices and modifying the maximum flow.</p>

<ds.algorithms><graph-theory><graph-algorithms><max-flow>
Efficient recalculation of the maximum flow when edge capacities are reduced
iheap
# Efficient recalculation of the maximum flow when edge capacities are reduced

(Asked by: username_0 on 2015-02-25)

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](https://cstheory.stackexchange.com/questions/9938/incremental-maximum-flow-in-dynamic-graphs) tries to tackle the related (harder?) problem of adding/removing vertices and modifying the maximum flow.

**Tags:** ds.algorithms, graph-theory, graph-algorithms, max-flow

---

## 1 answers

### Answer by username_1 on 2015-02-25. Score: 4 | Accepted 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.

> **Comments:**
> **username_2**: 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.  
> **username_1**: @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".  
> **username_2**: 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.  
> **username_0**: 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.  

---

