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?
6
-
$\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$– TassleCommented Aug 25, 2019 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$– leanderCommented Aug 25, 2019 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$– leanderCommented Aug 25, 2019 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$– TassleCommented Aug 25, 2019 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$– leanderCommented Aug 25, 2019 at 16:26
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
"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.
