<p>ok taking into account new info &amp; avoiding some tricky prior false start/red herring refs (mea culpa), here are some new refs on this.</p>

<p><a href="http://www.springerlink.com/content/tj122w6778812528/" rel="nofollow">Rapidly Solving an Online Sequence of Maximum Flow Problems with Extensions to Computing Robust Minimum Cuts</a>
Doug Altner and Özlem Ergun</p>

<p>this ref considers <em>online</em> sequences of MFPs and "warm starts" ie building on incremental chgs to a prior MFP. "We demonstrate that our algorithms reduce the running time by an order of magnitude when compared similar codes that use a black-box MFP solver. In particular, we show that our algorithm for robust minimum cuts can solve instances in seconds that would require over four hours using a black-box maximum flow solver."</p>

<hr>

<p><a href="http://smartech.gatech.edu/handle/1853/24828" rel="nofollow">advancements on problems involving maximum flows</a> Altner, Douglas S., georgia tech</p>

<p>in this 2008 Phd thesis (downloadable pdf) the author considers the problem of incrementally adding arcs which appears to be "close enough" to the problem of adding new vertices (with multiple new arcs). </p>

<p>much of this ref is concerned with deleting parts of the network (cuts/"interdiction") as stated in 1st part of abstract </p>

<p>see esp "IV SOLVING ONLINE SEQUENCES OF MAXIMUM FLOWS . . . . . . . p63".</p>

<p>p 63 "The goal
of this chapter, however, is to convince the reader that iteratively using a black-box
maximum flow solver to solve a large sequence of MFPs may lead to an enormous
number of unnecessary computations."</p>

<p>p66 "In the aforementioned applications, the MFPs are typically topologically similar.
That is, the next MFP in the sequence differs from the previous one by adding
or removing a small number of arcs or by predictably changing the capacities of
a localized arc set. Moreover, when solving these instances, the time and space
required to store anything beyond the solution to the previous problem is typically
unwarranted."</p>

<p>p67 author also uses the "warm start" approach here. "An effective strategy towards quickly solving an entire online sequence of optimization problems is to develop efficient reoptimization heuristics. To this end, we develop
a modified maximum flow algorithm that is designed for efficient warm starts.""</p>

<p>see esp p71 that has the specific incremental new-arc problem:</p>

<p>New Arc Maximum Flow Reoptimization Problem (NAMFRP)</p>

<p>the author considers the more general problems p67</p>

<p>Maximum Flow Reoptimization Problem (MFROP)<br>
Maximum Flow Single Arc Reoptimization Problem (MFSAROP)</p>

CC BY-SA 3.0
2012-02-07T17:35:32.650Z
2012-02-07T17:46:10.027Z
2012-02-07T17:46:10.027Z
vzn
<p>from some quick search it looks like the online version is an area of active research. you dont mention the application area which might help to narrow down the literature search. one option is to look for an application area where theres the most or latest innovation. hence there is some application of incremental max flow in vision systems &amp; some algorithms for it there; try <a href="http://research.microsoft.com/pubs/150437/ibfs-proc.pdf" rel="nofollow">Maximum Flows by Incremental Breadth-First Search</a> at microsoft research labs. paraphrasing the intro to this paper, apparently for vision instances the Boykov and Kolmogorov algorithm does well &amp; there are no known exponential time counterexamples although outside of the vision applications it might perform poorly. so it might be worth trying the B&amp;K algorithm on your data &amp; seeing how it performs &amp; also the microsoft algorithm.</p>

<p>you seem to be saying that an incremental algorithm that is linear in the number of graph edges is not sufficient speed? but isnt that fairly high efficiency? how many edges are you dealing with? maybe the approach might be to decrease cost of traversing the graph if that is expensive or a significant factor (eg graph stored in db vs graph stored in memory) </p>

<p>here is an interesting paper that argues that while the nonincremental algorithm for max flow is in P the incremental version is NP complete. "To the best of our knowledge our results are the first to find a P-time problem whose incremental version is NP complete."</p>

<p><a href="http://cornell.academia.edu/AlexaSharp/Papers/12406/Incremental_flow" rel="nofollow">Incremental flow</a> by Hartline, Sharp</p>

CC BY-SA 3.0
2012-02-06T17:35:48.867Z
Thanks, I didn't read your referenced papers, I'll take a look at them (I see some few papers before and found them useless), but about my problem area, It's an issue in real working situation in stock marketing. It's little bit complicated to say what happened when I found that I should solve this problem. In fact I didn't think it's hard at first glance but after trying some code I see it's not so easy. this algorithm will be run on mobile phones, they aren't so fast (and customers don't like my algorithm:). Also sometimes too many edges will be coming with new node. and this is bottleneck.
Saeed
CC BY-SA 3.0
2012-02-06T17:38:36.943Z
interesting. sounds like you should probably go with heuristics based on limited processing power and need for fast updates. can the processing be moved from the "client" (in your case apparently the phones) to the server instead? does every client have to compute a different version (ie different data) of the problem?
vzn
CC BY-SA 3.0
2012-02-06T18:14:54.107Z
In Iran, biggest problem is internet connection speed, So I can't move it to server side. If it was fine (good speed), for sure recalculating would not be bad.
Saeed
CC BY-SA 3.0
2012-02-06T19:26:19.987Z
ok roughly how many vertices/edges do you have? how are they represented? integers, floats, how many bytes?
vzn
CC BY-SA 3.0
2012-02-06T19:56:18.240Z
Vertices starting from zero (normally daily) and it will be grows to more than thousands node, graph is not highly connected, but In fact I can't have a guarantee for connectivity of graph, also numbers was decimal, I changed them to long, also I add some error possibility, e.g I ignored edge with smaller than `x` capacity (currently 10, it's changeable) to speed up algorithm, currently it's not bad but again sometimes customers make joke for it:)
Saeed
CC BY-SA 3.0
2012-02-06T20:41:32.620Z
I don't see how this answers the original question, which is about a graph that evolves over time by the addition of nodes and edges.  The first paper describes an incremental algorithm for the standard one-shot maxflow problem.  The second paper describes a paper for a _different_ "incremental maxflow" problem, where the set of edges is fixed but their capacities grow over time.
Jeffε
CC BY-SA 3.0
2012-02-06T20:59:34.143Z
@JɛﬀE, yes you are right :) in fact before that I see similar papers to referenced papers, but as you said they are not related to my problem, most close paper I see till now is what I referenced.
Saeed
CC BY-SA 3.0
2012-02-07T00:19:11.407Z
uh ok J staring at the papers more closely, guess you have a inescapable point and it looks like the authors are using "incremental" wrt "max flow" in a unexpected way. guess its a serious "gotcha" in attempting to study this particular q.... so get to be the bug instead of the windshield on this one =( am going to leave the answer in case anyone runs into the same trap, at least the comments are there. would change the answer to take all this into account but doubt its gonna save the score. re saeeds comment, he downgrades most papers as "useless" but surely some useful papers must exist..
vzn
CC BY-SA 3.0
2012-02-07T09:02:02.793Z
vzn, if I say useless I mean for my specific problem, for sure they are useful in other areas. Papers you referenced or papers I see them all was incremental max-flow, but their definition is not like mine (and non of two pair of them are same), I couldn't find better name for my problem :) If you know something better feel free to edit my Q.
Saeed
CC BY-SA 3.0
2012-02-06T16:52:01.747Z
2012-02-06T17:07:47.413Z
2012-02-06T17:07:47.413Z
vzn
<p>another possibility/direction is the <a href="http://en.wikipedia.org/wiki/Push-relabel_maximum_flow_algorithm" rel="nofollow">push-relabel maximum flow</a> algorithm which is "one of the most efficient algorithms for maximum flow" and can have better complexity profiles depending on your data. eg as the wikipedia page states</p>

<blockquote>
  <p>the implementation with FIFO vertex selection rule has $O(V^3)$ running time, the highest active vertex selection rule provides $O(V^2 \sqrt E$) complexity, and the implementation with Sleator's and Tarjan's dynamic tree data structure runs in $O(V \cdot E \cdot log(V^2 / E))$ time. asymptotically more efficient than Edmonds-Karp</p>
</blockquote>

CC BY-SA 3.0
2012-02-06T20:43:19.730Z
Again, I don't see how this answer is relevant to the posted question.  Push-relabel is a well-known textbook strategy for answering the standard maximum flow problem.
Jeffε
CC BY-SA 3.0
2012-02-07T00:24:14.907Z
so is ford-fulkerson... right? & OP asks for something better. do you know something that proves push-relabel is worse than ford-fulkerson? its not clear OP is familiar with push-relabel. geez, algorithm appearing in textbook is certainly not a immediate critera for rejecting the answer here, right?
vzn
CC BY-SA 3.0
2012-02-07T10:31:41.683Z
Actually, yes; questions that are answered in standard textbooks (or wikipedia) are not research-level.  However, the first posted question about incremental flows is interesting and definitely in scope.  (The lack of definitive answers suggests that the correct answer may be "Good question. Nobody knows.")
Jeffε
CC BY-SA 3.0
2012-02-08T10:54:08.327Z
vzn, thanks for your contribution, but : "do you know something that proves push-relabel is worse than ford-fulkerson" is not good reason to post it as answer, If you know why "push-relabel" in online algorithms is better than Ford-Falkerson is good to say it, I personally like Ford-Falkerson because of simplicity, low constant factor, and I know it from past. But as I said, I couldn't say it's good option in all cases, also these algorithms are not simply comparable, they need practical tests.
Saeed
CC BY-SA 3.0
2012-02-08T15:50:05.063Z
look the pt is that if you have one maximum flow algorithm that is not running well for your data, try another one esp one that is said to perform well because there are quite a few optimized for different data profiles. no it is not online/"vertex incremental" but it might perform better for the offline case if there is no alternative. the online versions while they exist as I found above, are prob going to be significantly difficult to implement...
vzn
CC BY-SA 3.0
2012-02-06T20:24:06.900Z
2012-02-06T20:24:06.900Z
vzn
<p>The described approach may not be theoretically optimal. It is just a simple practical solution that may work for the author. I can't provide any references because I always thought it is a widely known folklore, but strangely enough nobody posted it in the answer. So I do it.</p>

<p>Assume we have an undirected network $G=(V,E,c)$. Assume it is stored in a data structure which allows easy vertex/arc insertions/deletions. Sometimes we will use residual network $G_f$ (i.e. with updated capacities $c_f = c - f$).</p>

<p>First part is how to process vertex insertions/deletion. It's more or less straightforward for insertions:</p>

<ol>
<li>Add a new vertex with corresponding edges to the residual network.</li>
<li>Find a maximum flow in the updated residual network using a maxflow algorithm of your choice.</li>
</ol>

<p>For deletions things became more complicated. Imagine we split the vertex $v$ we are about to delete into 2 halves $v_{in}$ and $v_{out}$ such that all in-arcs points to $v_{in}$, all out-arcs goes from $v_{out}$ and this new vertices are connected by an arc of infinite capacity. Then deletion of $v$ is equivalent to deletion of the arc between $v_{in}$ and $v_{out}$. What will happen in this case? Let's denote by $f^v$ the flow passing through the vertex $v$. Then $v_{in}$ will experience excess of $f^v$ flow units and $v_{out}$ will experience shortage of $f^v$ flow units right after deletion (the flow constraints will be obviously broken). To make the flow constraints be held again we should rearrange flows, but also we want to keep the original flow value as high as possible. Let's see first if we can do rearrangement without decreasing the total flow. To check that find a maxflow $\tilde{f^v}$ from $v_{in}$ to $v_{out}$ in the "cutted" residual network (i.e. without the arc connecting $v_{in}$ and $v_{out}$). We should bound it by $f^v$ obviously. If it happen to be equal to $f^v$ then we are lucky: we have reassigned the flow which was passing through $v$ in such way that the total flow wasn't changed. In the other case the total flow must be decreased by "useless" excess of $\Delta = f^v - \tilde{f^v}$ units. To do that, temporarily connect $s$ and $t$ by an arc of infinite capacity and run maxflow algorithm again from $v_{in}$ to $v_{out}$ (we should bound flow by $\Delta$). That will fix residual network and make flow constraints be held again, automatically decreasing total flow by $\Delta$.</p>

<p>The time complexity of such updates may depend on maxflow algorithm we use. Worst cases may be pretty bad, though, but it's still better than total recalculating.</p>

<p>The second part is which maxflow algorithm to use. As far as I understand the author needs not very complex (but still efficient) algorithm with small hidden constant to run it on a mobile platform. His first choice of Ford-Fulkerson (I expect it to be <a href="http://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm" rel="nofollow">Edmonds-Karp</a>) looks not very bad from this point of view. But there are some other possibilities. The one I would recommend to try first is $O(|V|^2|E|)$ variant of <a href="http://en.wikipedia.org/wiki/Dinitz_blocking_flow_algorithm" rel="nofollow">Dinic's algorithm</a> because it's quite fast in practice and can be implemented in a very simple way. Other options may include capacity scaling Ford-Fulkerson in $O(|E|^2 \log C_{max})$ and, after all, different versions of push-relabel with heuristics. Anyway the performance will depend on a use case so the author should find the best one empirically.</p>

CC BY-SA 3.0
2012-02-13T15:44:39.957Z
After reading last vzn's answer I've found the similar approach described at the page 90 of [this](http://smartech.gatech.edu/bitstream/handle/1853/24828/altner_douglas_s_200808_phd.pdf?sequence=1).
Dmytro Korduban
CC BY-SA 3.0
2012-02-13T15:49:00.750Z
As I understand in removing node, By $\tilde{f^v}$ you will calculate flow in residual graph, but I think it's not true, in fact in residual graph you have some edges which used in calculating $f^v$ and you should add extra capacity to this edges, then calculating $\tilde{f^v}$, then using $\Delta$.
Saeed
CC BY-SA 3.0
2012-02-13T15:56:10.770Z
When you push 1 unit of flow from $v$ to $u$, you decrease $c_f(v,u)$ by 1 and increase $c_f(u,v)$ by 1 because the flow is anti-symmetric ($f(v,u) = -f(u,v)$). This defines true residual graph, so everything works well in it.
Dmytro Korduban
CC BY-SA 3.0
2015-01-28T10:11:51.340Z
Any ideas how you'd do this if you want to change an edge capacity?
Chet
CC BY-SA 3.0
2012-02-13T14:58:00.280Z
2012-02-18T15:40:10.707Z
2012-02-18T15:40:10.707Z
Dmytro Korduban
<p>I'm looking for a fast algorithm to compute maximum flow in dynamic graphs. i.e given a graph <span class="math-container">$G=(V,E)$</span> and <span class="math-container">$s,t\in V$</span> we have maximum flow <span class="math-container">$F$</span> in <span class="math-container">$G$</span> from <span class="math-container">$s$</span> to the <span class="math-container">$t$</span>. Then new/old node <span class="math-container">$u$</span> added/deleted with its corresponding edges to form a graph <span class="math-container">$G^1$</span>. What is a maximum flow in newly created graph? Is there a way to prevent from recalculating maximum flow?</p>
<p>Any preprocessing which isn't very time/memory consuming is appreciated.</p>
<p>Simplest idea is recalculating the flow.</p>
<p>Another simple idea is as this, save all augmenting paths which used in previous maximum flow calculation, for adding a vertex <span class="math-container">$v$</span>, we can find simple paths (in updated capacity graph by previous step) which start from source, goes to the <span class="math-container">$v$</span> then goes to the destination, but problem is, this path should be simple, I couldn't find better than <span class="math-container">$O(n\cdot m)$</span> for this case, for <span class="math-container">$m=|E|$</span>. (Also note that if it was just one path this could be done in <span class="math-container">$O(n+m)$</span> but it's not so.)</p>
<p>Also for removing node above idea doesn't work.</p>
<p>Also I already saw papers such as <a href="https://doi.org/10.1023/A:1023607406540" rel="nofollow noreferrer">Incremental approach for edges</a>, but seems they are not good enough in this case, it's more than <span class="math-container">$O(m)$</span> for each edge and seems is not suitable extension in this case (we just recalculate a flow). Also currently I'm using <a href="https://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm" rel="nofollow noreferrer">Ford-Fulkerson maximum flow algorithm</a> If there is better option for online algorithms, it's good to know it.</p>

CC BY-SA 3.0
2012-02-13T12:28:32.257Z
Could you please clarify "but problem is, this path should be simple" part? I didn't get it.
Dmytro Korduban
CC BY-SA 3.0
2012-02-13T12:36:53.083Z
@maldini.ua,In fact I mean, The path which goes from source to $v$ and then path from $v$ to destination shouldn't have common vertex (except $v$). Assume $v$ is new added node. If it wasn't so we can skip some checking and we can have faster algorithm (In average, or may be asymptotically).
Saeed
CC BY-SA 3.0
2012-02-13T12:52:24.740Z
Got it, but as for me it isn't something special about $v$. I think the simplest recalculating idea is the following: 1) add new vertex with edges to the [residual graph](http://en.wikipedia.org/wiki/Flow_network#Definition); 2) find maximum flow in the updated residual graph using a maximum flow algorithm of your choice. The case you suggested will be processed "automatically" by the maximum flow algorithm (say, it will not find any augmenting path etc.).

If you are interested in removing nodes, I can write it in answer.

P.S. To be clear, do you have directed or undirected graph?
Dmytro Korduban
CC BY-SA 3.0
2012-02-13T12:58:34.017Z
@maldini.ua, normal recalculating adds $|G|$ complexity to current solution, So I don't think it's good (may be is good by knowing that normally too many of edges are useless and in fact it doesn't cause to very high performance issue), but If you have idea about removing node, I'm interested to see your idea, Also graph is directed. P.S. but I'm interested in both cases.
Saeed
CC BY-SA 3.0
2012-02-13T13:15:14.183Z
Remember you run it in the residual graph, there should be a lot of edges of zero capacity at this time. Usually it works pretty fast especially in sparse graphs (it worked for me, at least). On the other hand the "simple path" approach sounds a bit like an extra sophistication for me. Also don't forget you have $O(|f||E|)$ bound on running time for the Ford-Fulkerson (where $|f|$ is bounded by the sum of $v$'s adjacent edges capacities).
Dmytro Korduban
CC BY-SA 3.0
2012-02-13T13:32:42.557Z
@maldini.ua, In residual graph assume all edges connected to destination has zero capacity, but all other edges has enough capacity, now you will add new node connected to too many of other nodes with enough capacity, and this new "bad node" connected to destination node with very big capacity, recalculating flow causes to bad performance, it's like recalculating flow in main graph, Also possibility of this case is not low, In fact when we can have more than thousands node in graph, in most cases there are bad nodes, and late coming of this node, causes to problem (Also in my way).
Saeed
CC BY-SA 3.0
2012-02-13T13:36:29.617Z
How "simple path" approach helps here? It's difficult to do something smart in this case anyway. =(
Dmytro Korduban
CC BY-SA 3.0
2012-02-13T13:47:40.037Z
let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/2479/discussion-between-saeed-and-maldini-ua)
Saeed
<graph-theory><graph-algorithms>
Incremental Maximum Flow in Dynamic graphs
Saeed
# Incremental Maximum Flow in Dynamic graphs

(Asked by: username_0 on 2012-01-27)

I'm looking for a fast algorithm to compute maximum flow in dynamic graphs. i.e given a graph $G=(V,E)$ and $s,t\in V$ we have maximum flow $F$ in $G$ from $s$ to the $t$. Then new/old node $u$ added/deleted with its corresponding edges to form a graph $G^1$. What is a maximum flow in newly created graph? Is there a way to prevent from recalculating maximum flow?

Any preprocessing which isn't very time/memory consuming is appreciated.

Simplest idea is recalculating the flow.

Another simple idea is as this, save all augmenting paths which used in previous maximum flow calculation, for adding a vertex $v$, we can find simple paths (in updated capacity graph by previous step) which start from source, goes to the $v$ then goes to the destination, but problem is, this path should be simple, I couldn't find better than $O(n\cdot m)$ for this case, for $m=|E|$. (Also note that if it was just one path this could be done in $O(n+m)$ but it's not so.)

Also for removing node above idea doesn't work.

Also I already saw papers such as [Incremental approach for edges](https://doi.org/10.1023/A:1023607406540), but seems they are not good enough in this case, it's more than $O(m)$ for each edge and seems is not suitable extension in this case (we just recalculate a flow). Also currently I'm using [Ford-Fulkerson maximum flow algorithm](https://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm) If there is better option for online algorithms, it's good to know it.

**Tags:** graph-theory, graph-algorithms

> **Comments:**
> **username_1**: Could you please clarify "but problem is, this path should be simple" part? I didn't get it.  
> **username_0**: @maldini.ua,In fact I mean, The path which goes from source to $v$ and then path from $v$ to destination shouldn't have common vertex (except $v$). Assume $v$ is new added node. If it wasn't so we can skip some checking and we can have faster algorithm (In average, or may be asymptotically).  
> **username_1**: Got it, but as for me it isn't something special about $v$. I think the simplest recalculating idea is the following: 1) add new vertex with edges to the [residual graph](http://en.wikipedia.org/wiki/Flow_network#Definition); 2) find maximum flow in the updated residual graph using a maximum flow algorithm of your choice. The case you suggested will be processed "automatically" by the maximum flow algorithm (say, it will not find any augmenting path etc.).  If you are interested in removing nodes, I can write it in answer.  P.S. To be clear, do you have directed or undirected graph?  
> **username_0**: @maldini.ua, normal recalculating adds $|G|$ complexity to current solution, So I don't think it's good (may be is good by knowing that normally too many of edges are useless and in fact it doesn't cause to very high performance issue), but If you have idea about removing node, I'm interested to see your idea, Also graph is directed. P.S. but I'm interested in both cases.  
> **username_1**: Remember you run it in the residual graph, there should be a lot of edges of zero capacity at this time. Usually it works pretty fast especially in sparse graphs (it worked for me, at least). On the other hand the "simple path" approach sounds a bit like an extra sophistication for me. Also don't forget you have $O(|f||E|)$ bound on running time for the Ford-Fulkerson (where $|f|$ is bounded by the sum of $v$'s adjacent edges capacities).  
> **username_0**: @maldini.ua, In residual graph assume all edges connected to destination has zero capacity, but all other edges has enough capacity, now you will add new node connected to too many of other nodes with enough capacity, and this new "bad node" connected to destination node with very big capacity, recalculating flow causes to bad performance, it's like recalculating flow in main graph, Also possibility of this case is not low, In fact when we can have more than thousands node in graph, in most cases there are bad nodes, and late coming of this node, causes to problem (Also in my way).  
> **username_1**: How "simple path" approach helps here? It's difficult to do something smart in this case anyway. =(  
> **username_0**: let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/2479/discussion-between-saeed-and-maldini-ua)  

---

## 4 answers

### Answer by username_1 on 2012-02-13. Score: 7 | Accepted answer

The described approach may not be theoretically optimal. It is just a simple practical solution that may work for the author. I can't provide any references because I always thought it is a widely known folklore, but strangely enough nobody posted it in the answer. So I do it.

Assume we have an undirected network $G=(V,E,c)$. Assume it is stored in a data structure which allows easy vertex/arc insertions/deletions. Sometimes we will use residual network $G\_f$ (i.e. with updated capacities $c\_f = c - f$).

First part is how to process vertex insertions/deletion. It's more or less straightforward for insertions:

1. Add a new vertex with corresponding edges to the residual network.
2. Find a maximum flow in the updated residual network using a maxflow algorithm of your choice.

For deletions things became more complicated. Imagine we split the vertex $v$ we are about to delete into 2 halves $v\_{in}$ and $v\_{out}$ such that all in-arcs points to $v\_{in}$, all out-arcs goes from $v\_{out}$ and this new vertices are connected by an arc of infinite capacity. Then deletion of $v$ is equivalent to deletion of the arc between $v\_{in}$ and $v\_{out}$. What will happen in this case? Let's denote by $f^v$ the flow passing through the vertex $v$. Then $v\_{in}$ will experience excess of $f^v$ flow units and $v\_{out}$ will experience shortage of $f^v$ flow units right after deletion (the flow constraints will be obviously broken). To make the flow constraints be held again we should rearrange flows, but also we want to keep the original flow value as high as possible. Let's see first if we can do rearrangement without decreasing the total flow. To check that find a maxflow $\tilde{f^v}$ from $v\_{in}$ to $v\_{out}$ in the "cutted" residual network (i.e. without the arc connecting $v\_{in}$ and $v\_{out}$). We should bound it by $f^v$ obviously. If it happen to be equal to $f^v$ then we are lucky: we have reassigned the flow which was passing through $v$ in such way that the total flow wasn't changed. In the other case the total flow must be decreased by "useless" excess of $\Delta = f^v - \tilde{f^v}$ units. To do that, temporarily connect $s$ and $t$ by an arc of infinite capacity and run maxflow algorithm again from $v\_{in}$ to $v\_{out}$ (we should bound flow by $\Delta$). That will fix residual network and make flow constraints be held again, automatically decreasing total flow by $\Delta$.

The time complexity of such updates may depend on maxflow algorithm we use. Worst cases may be pretty bad, though, but it's still better than total recalculating.

The second part is which maxflow algorithm to use. As far as I understand the author needs not very complex (but still efficient) algorithm with small hidden constant to run it on a mobile platform. His first choice of Ford-Fulkerson (I expect it to be [Edmonds-Karp](http://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm)) looks not very bad from this point of view. But there are some other possibilities. The one I would recommend to try first is $O(|V|^2|E|)$ variant of [Dinic's algorithm](http://en.wikipedia.org/wiki/Dinitz_blocking_flow_algorithm) because it's quite fast in practice and can be implemented in a very simple way. Other options may include capacity scaling Ford-Fulkerson in $O(|E|^2 \log C\_{max})$ and, after all, different versions of push-relabel with heuristics. Anyway the performance will depend on a use case so the author should find the best one empirically.

> **Comments:**
> **username_1**: After reading last username_2's answer I've found the similar approach described at the page 90 of [this](http://smartech.gatech.edu/bitstream/handle/1853/24828/altner_douglas_s_200808_phd.pdf?sequence=1).  
> **username_0**: As I understand in removing node, By $\tilde{f^v}$ you will calculate flow in residual graph, but I think it's not true, in fact in residual graph you have some edges which used in calculating $f^v$ and you should add extra capacity to this edges, then calculating $\tilde{f^v}$, then using $\Delta$.  
> **username_1**: When you push 1 unit of flow from $v$ to $u$, you decrease $c_f(v,u)$ by 1 and increase $c_f(u,v)$ by 1 because the flow is anti-symmetric ($f(v,u) = -f(u,v)$). This defines true residual graph, so everything works well in it.  
> **username_4**: Any ideas how you'd do this if you want to change an edge capacity?  

---

### Answer by username_2 on 2012-02-07. Score: -1

ok taking into account new info & avoiding some tricky prior false start/red herring refs (mea culpa), here are some new refs on this.

[Rapidly Solving an Online Sequence of Maximum Flow Problems with Extensions to Computing Robust Minimum Cuts](http://www.springerlink.com/content/tj122w6778812528/)
Doug Altner and Özlem Ergun

this ref considers *online* sequences of MFPs and "warm starts" ie building on incremental chgs to a prior MFP. "We demonstrate that our algorithms reduce the running time by an order of magnitude when compared similar codes that use a black-box MFP solver. In particular, we show that our algorithm for robust minimum cuts can solve instances in seconds that would require over four hours using a black-box maximum flow solver."

---

[advancements on problems involving maximum flows](http://smartech.gatech.edu/handle/1853/24828) Altner, Douglas S., georgia tech

in this 2008 Phd thesis (downloadable pdf) the author considers the problem of incrementally adding arcs which appears to be "close enough" to the problem of adding new vertices (with multiple new arcs).

much of this ref is concerned with deleting parts of the network (cuts/"interdiction") as stated in 1st part of abstract

see esp "IV SOLVING ONLINE SEQUENCES OF MAXIMUM FLOWS . . . . . . . p63".

p 63 "The goal
of this chapter, however, is to convince the reader that iteratively using a black-box
maximum flow solver to solve a large sequence of MFPs may lead to an enormous
number of unnecessary computations."

p66 "In the aforementioned applications, the MFPs are typically topologically similar.
That is, the next MFP in the sequence differs from the previous one by adding
or removing a small number of arcs or by predictably changing the capacities of
a localized arc set. Moreover, when solving these instances, the time and space
required to store anything beyond the solution to the previous problem is typically
unwarranted."

p67 author also uses the "warm start" approach here. "An effective strategy towards quickly solving an entire online sequence of optimization problems is to develop efficient reoptimization heuristics. To this end, we develop
a modified maximum flow algorithm that is designed for efficient warm starts.""

see esp p71 that has the specific incremental new-arc problem:

New Arc Maximum Flow Reoptimization Problem (NAMFRP)

the author considers the more general problems p67

Maximum Flow Reoptimization Problem (MFROP)  
Maximum Flow Single Arc Reoptimization Problem (MFSAROP)


---

### Answer by username_2 on 2012-02-06. Score: -3

from some quick search it looks like the online version is an area of active research. you dont mention the application area which might help to narrow down the literature search. one option is to look for an application area where theres the most or latest innovation. hence there is some application of incremental max flow in vision systems & some algorithms for it there; try [Maximum Flows by Incremental Breadth-First Search](http://research.microsoft.com/pubs/150437/ibfs-proc.pdf) at microsoft research labs. paraphrasing the intro to this paper, apparently for vision instances the Boykov and Kolmogorov algorithm does well & there are no known exponential time counterexamples although outside of the vision applications it might perform poorly. so it might be worth trying the B&K algorithm on your data & seeing how it performs & also the microsoft algorithm.

you seem to be saying that an incremental algorithm that is linear in the number of graph edges is not sufficient speed? but isnt that fairly high efficiency? how many edges are you dealing with? maybe the approach might be to decrease cost of traversing the graph if that is expensive or a significant factor (eg graph stored in db vs graph stored in memory)

here is an interesting paper that argues that while the nonincremental algorithm for max flow is in P the incremental version is NP complete. "To the best of our knowledge our results are the first to find a P-time problem whose incremental version is NP complete."

[Incremental flow](http://cornell.academia.edu/AlexaSharp/Papers/12406/Incremental_flow) by Hartline, Sharp

> **Comments:**
> **username_0**: Thanks, I didn't read your referenced papers, I'll take a look at them (I see some few papers before and found them useless), but about my problem area, It's an issue in real working situation in stock marketing. It's little bit complicated to say what happened when I found that I should solve this problem. In fact I didn't think it's hard at first glance but after trying some code I see it's not so easy. this algorithm will be run on mobile phones, they aren't so fast (and customers don't like my algorithm:). Also sometimes too many edges will be coming with new node. and this is bottleneck.  
> **username_2**: interesting. sounds like you should probably go with heuristics based on limited processing power and need for fast updates. can the processing be moved from the "client" (in your case apparently the phones) to the server instead? does every client have to compute a different version (ie different data) of the problem?  
> **username_0**: In Iran, biggest problem is internet connection speed, So I can't move it to server side. If it was fine (good speed), for sure recalculating would not be bad.  
> **username_2**: ok roughly how many vertices/edges do you have? how are they represented? integers, floats, how many bytes?  
> **username_0**: Vertices starting from zero (normally daily) and it will be grows to more than thousands node, graph is not highly connected, but In fact I can't have a guarantee for connectivity of graph, also numbers was decimal, I changed them to long, also I add some error possibility, e.g I ignored edge with smaller than `x` capacity (currently 10, it's changeable) to speed up algorithm, currently it's not bad but again sometimes customers make joke for it:)  
> **username_3**: I don't see how this answers the original question, which is about a graph that evolves over time by the addition of nodes and edges.  The first paper describes an incremental algorithm for the standard one-shot maxflow problem.  The second paper describes a paper for a _different_ "incremental maxflow" problem, where the set of edges is fixed but their capacities grow over time.  
> **username_0**: @JɛﬀE, yes you are right :) in fact before that I see similar papers to referenced papers, but as you said they are not related to my problem, most close paper I see till now is what I referenced.  
> **username_2**: uh ok J staring at the papers more closely, guess you have a inescapable point and it looks like the authors are using "incremental" wrt "max flow" in a unexpected way. guess its a serious "gotcha" in attempting to study this particular q.... so get to be the bug instead of the windshield on this one =( am going to leave the answer in case anyone runs into the same trap, at least the comments are there. would change the answer to take all this into account but doubt its gonna save the score. re saeeds comment, he downgrades most papers as "useless" but surely some useful papers must exist..  
> **username_0**: username_2, if I say useless I mean for my specific problem, for sure they are useful in other areas. Papers you referenced or papers I see them all was incremental max-flow, but their definition is not like mine (and non of two pair of them are same), I couldn't find better name for my problem :) If you know something better feel free to edit my Q.  

---

### Answer by username_2 on 2012-02-06. Score: -5

another possibility/direction is the [push-relabel maximum flow](http://en.wikipedia.org/wiki/Push-relabel_maximum_flow_algorithm) algorithm which is "one of the most efficient algorithms for maximum flow" and can have better complexity profiles depending on your data. eg as the wikipedia page states

> the implementation with FIFO vertex selection rule has $O(V^3)$ running time, the highest active vertex selection rule provides $O(V^2 \sqrt E$) complexity, and the implementation with Sleator's and Tarjan's dynamic tree data structure runs in $O(V \cdot E \cdot log(V^2 / E))$ time. asymptotically more efficient than Edmonds-Karp

> **Comments:**
> **username_3**: Again, I don't see how this answer is relevant to the posted question.  Push-relabel is a well-known textbook strategy for answering the standard maximum flow problem.  
> **username_2**: so is ford-fulkerson... right? & OP asks for something better. do you know something that proves push-relabel is worse than ford-fulkerson? its not clear OP is familiar with push-relabel. geez, algorithm appearing in textbook is certainly not a immediate critera for rejecting the answer here, right?  
> **username_3**: Actually, yes; questions that are answered in standard textbooks (or wikipedia) are not research-level.  However, the first posted question about incremental flows is interesting and definitely in scope.  (The lack of definitive answers suggests that the correct answer may be "Good question. Nobody knows.")  
> **username_0**: username_2, thanks for your contribution, but : "do you know something that proves push-relabel is worse than ford-fulkerson" is not good reason to post it as answer, If you know why "push-relabel" in online algorithms is better than Ford-Falkerson is good to say it, I personally like Ford-Falkerson because of simplicity, low constant factor, and I know it from past. But as I said, I couldn't say it's good option in all cases, also these algorithms are not simply comparable, they need practical tests.  
> **username_2**: look the pt is that if you have one maximum flow algorithm that is not running well for your data, try another one esp one that is said to perform well because there are quite a few optimized for different data profiles. no it is not online/"vertex incremental" but it might perform better for the offline case if there is no alternative. the online versions while they exist as I found above, are prob going to be significantly difficult to implement...  

---

