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

<p>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'$. </p>

<p>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''$.</p>

<p>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.</p>

CC BY-SA 3.0
2016-05-06T04:34:43.763Z
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'')?
Benjamin Tillman
CC BY-SA 3.0
2016-05-06T14:17:21.107Z
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.
sbzk
CC BY-SA 3.0
2016-05-05T17:55:44.300Z
2016-05-05T17:55:44.300Z
sbzk
<p>I'm wondering: given a fixed graph G, if we're to calculate the max flow between the vertices <em>s</em> and <em>t</em>, how different is the problem to calculate the max flow between the vertices <em>s'</em> and <em>t</em>, or similarly, <em>s</em> and <em>t'</em> (on the same graph)?</p>

<p>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.</p>

<p>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?</p>

<p>Any pointers at all would be most welcome :)</p>

<graph-theory><graph-algorithms><max-flow>
Max network flow with arbitrary source / sink
Benjamin Tillman
# Max network flow with arbitrary source / sink

(Asked by: username_0 on 2016-05-05)

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

**Tags:** graph-theory, graph-algorithms, max-flow

---

## 1 answers

### Answer by username_1 on 2016-05-05. Score: 3 | Accepted answer

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.

> **Comments:**
> **username_0**: 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'')?  
> **username_1**: 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.  

---

