# Max network flow with arbitrary source / sink

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

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