Incremental Maximum Flow in Dynamic graphs

Question

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.

Answer 1

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.

Answer 2

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)

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

Answer 4

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