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.
Incremental Maximum Flow in Dynamic graphs
graph theory;graph algorithms
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:Add a new vertex with corresponding edges to the residual network.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.