Does there exist a flow graph that always requires flow to be pushed back no matter what ordering of augmenting paths is chosen in Ford Fulkerson?

Let's assume we use the standard procedure of repeating this step:

  1. Find an augmenting path $p$ in residual graph $G_R$ of $G$.
  2. Let $c$ be the minimum capacity edge in $p$.
  3. Increase the flow on every edge in $p$ by $c$.
  4. Update $G_R$.

The key here is step 1, where select augmenting paths. For many graphs, if we had an oracle to tell us which augmenting paths to use, we would never need to push flow back. I'm am curious if there is a case for which, regardless of augmenting paths and their orders, we will always be required to "push flow back". To clarify what I mean:

To push flow back in $G$, means to increase the flow on an edge $(u,v)$ in $G_R$ such that edge $(v,u)$ exists in $G$.

If this is not possible, I would also be interested in a proof that such ordering of augmenting paths always exists? If it is possible, does it generalize to any number of nodes $n$? This question is alluded at in the ending sentences of this answer, but provides no proof.

My initial thoughts were that this would be a trivial proof. However, there are many times when the optimal flow along an augmenting path may not be equivalent to its minimum capacity edge. Since (by step 3) we require paths to be filled to their minimum capacity, we cannot easily meet this. My next thought would be that there should exist at least one augmenting path such that its max flow is equivalent to its minimum capacity edge. This is obvious by the Max flow min cut Theorem, but I am not sure how this would apply to the proof. With this, we may be able to get an inductive proof that it is always possible, but I am really unsure of this strategy as well. Any help would be appreciated.

  • $\begingroup$ A nice example from ryan that shows not every max flow can be decomposed in this way: i.stack.imgur.com/d4ObI.png (though in this case there is another max flow that can be decomposed). $\endgroup$ – D.W. Apr 26 at 23:22
  • $\begingroup$ My strategy would be to ask whether there always exists a maximum flow that can be represented as a sum of path flows, with the additional condition that each path must make some edge tight in the flow graph that still remains after all preceding paths have been applied. Induction on the edge count of the input graph could be useful here, since every such path must then remove at least one edge from the flow graph. $\endgroup$ – j_random_hacker Apr 27 at 15:49
  • $\begingroup$ @xskxzr: Whoops, my mistake. $P_1 \ne P_2$ is also required I believe. It seems correct to me, but do you have a proof sketch? I can see how a specific pair of paths in a bad flow can be fixed, but my concern is that fixing these paths might disrupt previously-fixed paths. $\endgroup$ – j_random_hacker Apr 27 at 20:02
  • $\begingroup$ @j_random_hacker My previous guess seems wrong. Now I have a new guess. Call a flow extreme if there does not exist two positive cycles $v_1v_2\ldots v_nv_1$ and $v_1v_n\ldots v_2v_1$ at the same time in the residual network. There always exists an extreme max flow. My guess: If a max flow is extreme, it can be decomposed. $\endgroup$ – xskxzr Apr 28 at 12:34
  • $\begingroup$ @xskxzr: That again sounds plausible, but do you have a proof in mind? How can we be sure that fixing one cycle does not unfix another? Induction on cycle size perhaps? $\endgroup$ – j_random_hacker Apr 28 at 13:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.