3
$\begingroup$

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"?

$\endgroup$
  • 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 '16 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 Zanden Feb 10 '16 at 13:47
3
$\begingroup$

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.

enter image description here

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.

$\endgroup$
  • $\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$ – Tom van der Zanden Feb 10 '16 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$ – Shreesh Feb 10 '16 at 9:45
  • $\begingroup$ Moreover, his question is related only to Ford-Fulkerson method. $\endgroup$ – Shreesh Feb 10 '16 at 10:41
  • $\begingroup$ @shreesh When you say "Proof follows from min-cut max-flow theorem.", can you elaborate? $\endgroup$ – user270494 Feb 10 '16 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$ – Shreesh Feb 11 '16 at 11:23

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.