1
$\begingroup$

Suppose we have a graph $G(E,V)$ with a source node $s$. Now for any $t\in V \setminus s$ I can find the maximum flow from $s$ to all possible $t$ by using the Ford Fulkerson algorithm $|V|-1$ times, once for each $t$. I feel like there must be a faster way to compute all $|V|-1$ max flows that makes use of dynamic programming techniques. Any ideas?

$\endgroup$
  • $\begingroup$ Are you trying to get only the maximum among all those flows or do really want to compute every single s-t flow for some fixed s? $\endgroup$ – Tassle Aug 25 at 15:30
  • $\begingroup$ Thanks for the question. I am interested in every single one, but if there is a an algorithm that only returns the maximum out of all of them I would also be interested. However, I would guess that the maximum flow vertex will almost always be a vertex very close to $s$. $\endgroup$ – leander Aug 25 at 15:43
  • $\begingroup$ Basically I am trying to rank the nodes with respect to the maximum flow that can reach them. Later on I am planning to select one of them based on a different set of criteria. $\endgroup$ – leander Aug 25 at 15:44
  • $\begingroup$ For the maximum out of all of them, I think "J. Hao and J. B. Orlin. A faster algorithm for finding the minimum cut in a directed graph." might be of interest. They provide an algorithm to compute the min cut for a fixed s on the source side with time-complexity O(nm log(n²/m)) (which is the maximum s-t flow for fixed s) (Edit: The time complexity is equal to a single run of Push-Relabel with dynamic trees. I haven't read the paper but you might be able to plug in Ford-Fulkerson instead of Push-Relabel and get the time-complexity of a single FF run) $\endgroup$ – Tassle Aug 25 at 16:11
  • $\begingroup$ Ah, amazing! That's it! If you post this as an answer I can accept it. Thank you so much. $\endgroup$ – leander Aug 25 at 16:26
0
$\begingroup$

"J. Hao and J. B. Orlin. A faster algorithm for finding the minimum cut in a directed graph." provides an algorithm to compute the min cut for a fixed s on the source side with time-complexity $O(nm \log(n^2/m))$, by reducing the complexity of multiple s-t cuts for varying sinks to the complexity of a single call to the Push-Relabel max-flow algorithm.

This might be adaptable to a version where you can store all the intermediate min-cut values (=max-flow values) for all sinks along the way.

$\endgroup$

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.