I am told that with every flow network, the Ford-Fulkerson algorithm produces an execution that never decreases the value of the flow on any of the edges (i.e. never “pushes back” the flow on any of the edges). I am wondering how that can be possible. Can we choose augmenting paths that allow us to never "push back"?
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ Who tells you this? It's wrong. Please reference your source. (If it were true, greedy approaches would work. We know they don't, that's why we need the whole business with residual networks in the first place.) $\endgroup$– Raphael ♦Feb 10, 2016 at 13:03
-
$\begingroup$ Since FF doesn't specify how augmenting paths are found, I think the question should be interpreted as "for every flow network, there exists an execution of FF that never pushes back flow" - where we're allowed to specify at each stage of the algorithm which augmenting path should be used. $\endgroup$– Tom van der ZandenFeb 10, 2016 at 13:47
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
No, it is not true that "the Ford-Fulkerson algorithm produces an execution that never decreases the value of the flow on any of the edges". If you look at the wiki article of Ford and Fulkerson method you will see the following pseudocode:
Algorithm Ford–Fulkerson
Inputs: Given a Network $G = (V,E)$ with flow capacity $c$, a source node $s$, and a sink node $t$
Output: Compute a flow $f$ from $s$ to $t$ of maximum value
$f(u,v) \leftarrow 0$ for all edges $(u,v)$
While there is a path $p$ from $s$ to $t$ in $G_f$, such that $c_f(u,v) > 0$
for all edges $(u,v) \in p$:
Find $c_f(p) = \min\{c_f(u,v) : (u,v) \in p\}$
for each edge $(u,v) \in p$
$f(u,v) \leftarrow f(u,v) + c_f(p)$ (Send flow along the path)
$f(v,u) \leftarrow f(v,u) - c_f(p)$ (The flow might be "returned" later)
In the last line $f(v,u)$ is clearly decremented.
In the example below one will have to decrease flow in the middle edge to get max-flow. There is no other way.
If you want to know, if there exist a sequence of augmenting paths that never decrease the flows, then the answer is possibly yes. Proof might be non-trivial though.
answered Feb 10, 2016 at 8:38
-
$\begingroup$ This answer is based on a misreading of the question. The question is "does there exist an execution that doesn't bush back flow?" rather than "do all executions not push back flow?". My gut feeling is that it is true (where pushing back flow is interpreted as actually decreasing the value of flow where it was previously increased). $\endgroup$ Feb 10, 2016 at 9:16
-
$\begingroup$ I think I understood the quetion correctly. He says "never decreases the value of the flow on any of the edges", which is not correct. Then comes the second part of the question, where he asks, how "Can we choose augmenting paths that allow us to never push back?" to ensure his incorrect assumption. $\endgroup$ Feb 10, 2016 at 9:45
-
$\begingroup$ Moreover, his question is related only to Ford-Fulkerson method. $\endgroup$ Feb 10, 2016 at 10:41
-
$\begingroup$ @shreesh When you say "Proof follows from min-cut max-flow theorem.", can you elaborate? $\endgroup$ Feb 10, 2016 at 20:06
-
$\begingroup$ Since proof seemed to be tough, I have modified the statement to only talk about the possibility. Probably will need to check exponential number of augmenting paths to choose one which will not reverse flow. But even with minimum residual flow augmented path, I could not complete the proof. So I gave up. $\endgroup$ Feb 11, 2016 at 11:23