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:
- Find an augmenting path $p$ in residual graph $G_R$ of $G$.
- Let $c$ be the minimum capacity edge in $p$.
- Increase the flow on every edge in $p$ by $c$.
- 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.