1
$\begingroup$

I'm wondering: given a fixed graph G, if we're to calculate the max flow between the vertices s and t, how different is the problem to calculate the max flow between the vertices s' and t, or similarly, s and t' (on the same graph)?

I've just started reading a paper by Altner and Ergun -- Rapidly Solving an Online Sequence of Maximum Flow Problems -- where they discuss a method to efficiently recalculate the max flow of a graph given small pertubations in the topology of that graph (for example, deleting or adding an edge). They do this by using the results from the previous max flow as a 'warm start' to calculating the new max flow.

I'm wondering if there is a similar story for recalculating the max flow given a change in source or sink? That is, is it possible to 'warm start' a max flow problem when a different source or sink is chosen?

Any pointers at all would be most welcome :)

$\endgroup$
3
$\begingroup$

Finding max flow from arbitrary source/sink can be reduced to finding max flow under insertion/deletion of edges.

We modify the graph by adding two vertices $s^*$ and $t^*$ not connected to any vertex. We maintain the data structure to compute max flow from $s^*$ to $t^*$ under insertion/deletion of edges. Now, whenever we want to calculate max flow from any source $s'$ to any sink $t'$, we simply add edges $(s^*,s')$ and $(t',t^*)$ with infinite capacity. The max flow from $s^*$ to $t^*$ would then essentially be the max flow from $s'$ to $t'$.

In case you want to change the source and sink to $s''$ and $t''$ respectively, simply delete $(s^*,s')$ and $(t',t^*)$ and add $(s^*,s'')$ and $(t'',t^*)$. The max flow from $s^*$ to $t^*$ would now represent the max flow from $s''$ to $t''$.

This technique was earlier used to show the equivalence of All Pair Shortest Path and Single Source Shortest Path in the dynamic environment. Similarly, it can also show equivalence of All Pair Reachability and Single Source Reachability in the dynamic environment.

$\endgroup$
  • $\begingroup$ Thanks very much. Are there any papers that discuss this, in particular, how useful can we expect the max flow from s* to t* (via s' and t' respectively) will be to the max flow from s* to t* (this time via s'' and t'')? $\endgroup$ – Benjamin Tillman May 6 '16 at 4:34
  • $\begingroup$ It would be as useful as the one with changed edges (the paper by Altner and Ergun). Because it directly reduces to that problem. Hence, the same technique by Altner and Ergun can be used here. $\endgroup$ – sbzk May 6 '16 at 14:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.