13
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • 1
    $\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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 at 13:04

2 Answers 2

Reset to default
0
$\begingroup$

I think it is possible to reason backwards from an optimal solution$^1$ to the order in which the paths have to be augmented to not have any pushing-back:

In the solution, for any path from the source to the sink, where the flow is larger than zero, there is at least one edge, that constrains that flow, i.e: its flow is at capacity. If it were not, there would have been an augmenting path along that path, i.e. the solution would not be optimal. Also, of the edges that are at capacity, there has to be one (or multiple) with the lowest possible capacity. Furthermore, this edge has to be part of some path between source and sink where each edge has a flow at least as high. We take such a path, call it $P_1$ and remove its 'flow capacity' from the initial graph (i.e. reduce the capacity of the edges along the path). We repeat this with the remaining graph (resulting in $P_2, P_3, \ldots, P_n$) until there is no path between source and sink remaining, where all edges have a non-zero capacity.

Then, $P_1, P_2, \ldots, P_n$ is the order in which the paths have to be chosen s.t. there is never any pushing back necessary.

$1$: This only holds for optimal solutions that have been found with the FF algorithm. E.g. in a graph where 5 edges with capacity 2 go into node X and only one edge leaves it with capacity 5, there would be a max flow where each of the 5 edges has a flow of 1/2 and the outgoing has a flow of 5/5. Then the 5/5 edge would be the lowest edge at capacity but there is no path from source to sink in that graph where each edge has a flow of 5 or more. This is no problem for the algorithm outlined above because such a max-flow solution would not be found with FF.

Improve this answer
$\endgroup$
12
  • $\begingroup$ Thinking about this some more, I think you need to show more explicitly that, after removing $P_1$'s flow from the capacity of the graph, we are left with a smaller instance of the same situation as we started with, namely an optimal solution to a flow problem. This isn't too hard, I think: The new graph is at least 1 edge smaller, since at least 1 edge in $P_1$ was tight; and the new flow is feasible, since the original one was and every internal vertex in $P_1$ is incident on 2 edges of $P_1$ that add and subtract the same amount of flow, leaving the excess at that vertex at 0. ... $\endgroup$
    – j_random_hacker
    Oct 26, 2019 at 11:38
  • $\begingroup$ ... Finally, to establish optimality, the usual "suppose there was some better flow in the new graph, then we could add $P_1$ to that to produce a better flow in the original graph than we started with, but we assumed what we had was optimal -- contradiction!" argument works. :) $\endgroup$
    – j_random_hacker
    Oct 26, 2019 at 11:40
  • 2
    $\begingroup$ So how to prove such a max-flow solution would not be found with FF? Or more formally, how to prove that in a FF solution, there exists an edge that is at capacity being part of some path between source and sink where each edge has a flow at least as high? $\endgroup$
    – xskxzr
    Oct 27, 2019 at 5:23
  • 1
    $\begingroup$ 1. Where does your proof use the assumption that the solution has been found with FF? You say it only works for such solutions, but then I can't find any sentence in your proof that uses this assumption. 2. You claim that "this edge has to be part of some path between source and sink where each edge has a flow at least as high", but I think this needs a proof. Is it true? Here's a max flow (not found by FF) where it is false: i.stack.imgur.com/d4ObI.png. So you'll need to use the assumption that the solution was found by FF somewhere; but what exactly is the reasoning? (cont.) $\endgroup$
    – D.W. ♦
    Oct 30, 2019 at 17:04
  • 1
    $\begingroup$ @j_random_hacker, I don't think it's enough to show that the new graph is an optimal solution to a flow problem; we also need to show that it's a solution that could have been found by FF. Some optimal solutions can't be found by FF, and the proof doesn't work for those (e.g., i.stack.imgur.com/d4ObI.png). It seems like there are some gaps in this proof attempt that I'm not sure how to fill in. $\endgroup$
    – D.W. ♦
    Oct 30, 2019 at 17:08
0
$\begingroup$

It is not hard to show that every graph admits such a sequence of augmenting paths where no push-backs are needed. However, this is not the case if the augmenting paths we are looking for are necessarily shortest augmenting paths. I will sketch the idea behind the former, keeping it as an exercise for you to find an example of the later.

Let $G$ be a given graph. Let $c: E \mapsto \mathbb{Z}$ be the given function of capacities and let $f_M : E \mapsto \mathbb{Z}$ be a maximum flow in $G$ (We only need its existence and do not care how to compute it). Let us apply the method of Ford and Fulkerson on the graph $G$ where we assign the function $f_M$ as the capacities of the edges. Let $P_1, \dots P_r$ be the augmenting paths in the graph in order. We claim that these paths never introduce a push-back and that for the graph $G$ with capacities function $c$, the paths $P_i$ are augmenting path in $G$ after augmenting $P_1$ to $P_{i-1}$.

The first claim can be proven by induction over $i$, showing that for $f_i$ the flow function after $i$ steps, that $f_i < f_M$ and hence is part of the final answer and using this fact to prove the claim.

The second claim comes from the fact that each augmenting path in $G$ where the capacities are $f_M$ admits a critical edge that is also critical when the capacities are defined by the function $c$.

Note that these proofs are not formal, I only sketched the idea and I keep the task of formulizing a complete proof as an excersize for you :)

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ For the first claim, I don't see how it's enough to show that $f_i < f_M$ for each $f_i$ -- IIUC, this would still permit downward fluctuations in the flow across a given edge as $i$ advances. $\endgroup$
    – j_random_hacker
    Oct 23, 2019 at 6:27

Your Answer

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

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