10

I'm looking for fast algorithm to compute maximum flow in dynamic graphs (adding/deleting node with related edges to graph). i.e we have maximum flow in G now new node added/deleted with related edges, I don't like to recalculate maximum flow for new graph, in fact, I want use previous available results for this graph.

Any preprocessing which isn't very time/memory consumer is appropriated.

Simplest idea is recalculating the flow.

Another simple idea is as this, save all augmenting paths which used in previous maxflow calculation, now for adding vertex v, we can find simple paths (in updated capacity graph by previous step) which start from source, goes to v then goes to destination, but problem is this path should be simple, I couldn't find better than O(n*E) for this case. (if it was just one path or paths was disjoint, this can be done in O(n+E), but it's not so).

Also for removing node above idea doesn't work.

Also my question is not related to another question which looks on dynamic edges adding/removing.

Community
  • 1
  • 1
Saeed Amiri
  • 22,252
  • 5
  • 45
  • 83
  • How is your question not related to the link you gave? It seems spot on to me. – Keith Randall Jan 26 '12 at 20:01
  • @KeithRandall, my question is about adding deleting vertex, but that question was about edges, in fact with one vertex you probably will add `n` edges, so vertex case is more complicated than edge case, e.g I can have some intuition with edges, but my best solution for vertices is not good solution. – Saeed Amiri Jan 26 '12 at 21:38
  • @Charles, would you describe why you removed max-flow tag? I added this tag to SO because it's useful. specially in searches. – Saeed Amiri Jan 26 '12 at 21:41
  • edges are what matters, adding or removing a vertex with no edges is trivial. So maybe you're asking if there is a more efficient incremental algorithm to add `n` edges all connected to a single vertex, than running the linked incremental edge algorithm `n` times? – Keith Randall Jan 26 '12 at 22:21
  • @Saeed, the term "maximum flow" is generic and ill-defined to outsiders. Perhaps consider adding a tag wiki, picking a more precise name for the tag (maybe "maximum-flow" instead of just "max-flow"?), and going through other questions here on SO and adding it where relevant. Taking these steps will dissuade new tag deletionists such as myself from removing it in the future. – Charles Jan 26 '12 at 22:34
  • @Charles, IMO If you expect someone do so, you should mention in your edit, no one can think about your idea, Also creating new tag doesn't have such a complicated rule, Also programmers know this as max-flow, if you look at their code I'm pretty sure high amount of their function name is max_flow, MaxFlow, maxFlow, ... not maximumFlow,.... – Saeed Amiri Jan 27 '12 at 00:04
  • @KeithRandall, not exactly, my question basically differs from that ones, if you can convert it to that one, provide it as answer. (In fact now is my sleep time and is little hard to show differences in detail). – Saeed Amiri Jan 27 '12 at 00:05

3 Answers3

1

For adding Vertex v,Use the old Flow f and compute the Residual Graph, then get an Augmenting Path by DFS OutDeg(v) times.

For removing a Vertex v - compute all the flow thats leaving v, say the sum of flow leaving v is a, then while (a>0) find a path P from s to t that is going thro v, and reduce f(P) from the flow and from a.

i think that should help... im more sure on the addition then on the remove, so id love to get corrected in comments :)

Ofek Ron
  • 8,354
  • 13
  • 55
  • 103
  • Good offer but your approach for adding vertex takes O(n*E) in worst case, Also your remove option takes O(n*E) Also I don't think is right way, but your adding approach is simpler than mine. – Saeed Amiri Feb 12 '12 at 06:11
  • I dont think you can do anything better then that... are you sure there is a better way? notice that outdeg(v) not likely to be so high in most graphs, so its avarge case should run in O(E)... – Ofek Ron Feb 12 '12 at 09:15
  • No average shouldn't be O(E), in average (with random graphs) you will have degree around n/2 for new vertices. but currently I think your algorithm has some bug, It's not essentially use degree(v) time calculation, may be we need more than this (in cases when you traverse one new added edge more than one time). Also I don't think there is an straight forward algorithm, but ask it here to see if anyone has good idea? – Saeed Amiri Feb 12 '12 at 12:04
  • you are right, more correctly put is that the complexity will be O(delta*E) where delta is the diffrence f'-f, where f' is the ending flow. assuming we got an integer flow. – Ofek Ron Feb 12 '12 at 12:50
  • I have decimal numbers not integers, but your suggested `O` is not tight but not bad :) – Saeed Amiri Feb 12 '12 at 13:01
0

To dynamically add a vertex v and its associated edges E:

1) Add v by itself to the graph. Since it has no edges, it cannot affect the maximum flow.

2) Add the associated edges E to the graph, one at a time, using the algorithm from this question

Do the reverse for deleting a vertex and its associated edges.

Community
  • 1
  • 1
Keith Randall
  • 22,985
  • 2
  • 35
  • 54
  • 1
    -1 Do you know order of that algorithm? it's more than O(E) for each edge in fact it's not good (my own algorithm is more simple and faster), Also this (what you offered) doesn't cover the deletion of node. – Saeed Amiri Jan 27 '12 at 09:07
0

I asked this question in CSTheory.StackExchange, For Adding node as I discussed with others I found recalculating is faster than other known algorithms, because recalculation runs on semi sparse graph (residual graph) so it's fast enough also for removing node, there was a good answer, dividing node (which wants to be removed) into two sets, v_in and v_out and calculating flow on residual graph from v_in to v_out, and again calculating flow in residual graph from v_in to v_out by adding infinite edge between source and destination. (and finally comparing their difference and updating residual graph). You can see related Q/A and discussions in Incremental Maximum Flow in Dynamic graphs.

Community
  • 1
  • 1
Saeed Amiri
  • 22,252
  • 5
  • 45
  • 83