# Incremental Maximum Flow in Dynamic graphs

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, 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 If there is better option for online algorithms, it's good to know it.

• Could you please clarify "but problem is, this path should be simple" part? I didn't get it. – Dmytro Korduban Feb 13 '12 at 12:28
• @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 Feb 13 '12 at 12:36
• 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; 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 Feb 13 '12 at 12:52
• @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 Feb 13 '12 at 12:58
• 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 Feb 13 '12 at 13:15

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

• After reading last vzn's answer I've found the similar approach described at the page 90 of this. – Dmytro Korduban Feb 13 '12 at 15:44
• 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 Feb 13 '12 at 15:49
• 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 Feb 13 '12 at 15:56
• Any ideas how you'd do this if you want to change an edge capacity? – Chet Jan 28 '15 at 10:11

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 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 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)

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 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 by Hartline, Sharp

• 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 Feb 6 '12 at 17:35
• 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 Feb 6 '12 at 17:38
• 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 Feb 6 '12 at 18:14
• 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ε Feb 6 '12 at 20:41
• @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 Feb 6 '12 at 20:59

another possibility/direction is the push-relabel maximum flow 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

• 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ε Feb 6 '12 at 20:43
• 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 Feb 7 '12 at 0:24
• 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ε Feb 7 '12 at 10:31
• 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 Feb 8 '12 at 10:54
• 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 Feb 8 '12 at 15:50