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.

up vote 4 down vote accepted

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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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