Why are back edges required in the Ford-Fulkerson algorithm?

Question

To find the maximum flow in a graph, why doesn't it suffice to only saturate all augmenting paths with the minimum edge capacity in that path without considering the back edges? I mean, what is the point calling it a back edge if we assume flow from it?

Weapon

Answer 1

Back edges are necessary when doing the Ford-Fulkerson algorithm in case the path that you choose ends up not being a part of the overall flow.

As an example where back edges are necessary, consider this flow network:

    s
   / \
  a   b
   \ / \
    c   d
     \ /
      t

Assume that all edges point down and that all edges have capacity 1 and that you want to find a flow from s to t. Suppose on the first iteration of Ford-Fulkerson that you take the path s → b → c → t. At this point, you've pushed one unit of flow from s to t. If you don't add in any back edges, you're left with this:

    s
   / 
  a   b
   \   \
    c   d
       /
      t

There are no more s-t paths, but that doesn't mean you have a max flow. You can push two units of flow from s to t by sending one along the path s → a → c → t and the other along the path s → b → d → t. Without any back edges in the residual flow network, you would never discover this other path.

Hope this helps!

Inanity

Can you please go into more detail as to what would make up the backedges in your specific case? Thank you! – Grindery

@bluejamesbond Here, the back edges would point from b to s, from c to b, and from t to c (it's the reverse of the edges that were along the path taken). Those edges then give an augmenting path from s to t that shows that the flow isn't maximum. – Inanity

When will it take those paths however? – Grindery

Which paths are you referring to? – Inanity

The residual edges you added are now in the graph. But, how will the next iteration of FordF using BFS/DFS take that into consideration because there is no path between S and T even if there is a back edge. Update: I see it now, being an idiot there. My bad! – Grindery

I have a basic question , if the above graph is directed , after adding back ekdge ..second flow would be s->a->c -> b -> d ->t of capacity 1, so max flow is 2 , which is fine ... but if compared to real life example of pipe connecting their is no pipe between c->b , so how does it work ? – Establishmentarian

Amazing how a simple example can clarify the entire algorithm. – Babbage

This was the best example I've ever found which clarifies the logic behind back edges in the residual graph. – Babar

@LalitaKumar I am late, but for future readers, that means the amount of flow in back edge(c->b) never happened in (b->c), i.e, in this example it would mean there never was any flow in b->c. – Chancy