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

  • 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$ Feb 10, 2016 at 13:47
  • $\begingroup$ @TomvanderZanden, in fact, there is a flow network that forces Ford-Fulkerson to push flow back, regardless of how it chooses the paths. See cs.stackexchange.com/a/167470/4678. $\endgroup$
    – Neal Young
    Apr 6 at 20:57

1 Answer 1


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.

  • $\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$
    – user270494
    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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.