Why must back-edges be taken into account in Edmonds-Karp Maximum Flow?

Question

I was trying to implement Edmonds-Karp in C++ for maximum flow, and I wrote it slightly differently:

1. Instead of going through all edges in residual graph, I only went through the edges that are present in the original graph, using the adjacency list.
2. I did not update any back-edges when updating the residual graph with min flow.

Interestingly, when I ran my code, it gave me correct results. So I went to Wikipedia's example, where it specifically show how a back-edge is being used. When I fed this graph to my code, I got the correct answer again. I also checked the resultant flow matrix, and it was identical to Wikipedia's.

Can someone explain why we must add and update back-edges, and maybe give an example where they are critical?

Here's the code that I wrote (updated to include back edges):

Arvie

Just to be sure to understand well, does it mean that when you take an arc in the reverse way, you do not update the value of the flow on this arc ? – Ruth

@DamienProt I had this idea that instead of iterating through the residual graph, I go through only the original adjacency list. So I never visit any back edge, and saw no point updating any. – Arvie

Answer 1

Consider the following flow network

Suppose the first flow is s → u → v → t. (If you object that that the BFS of Edmonds-Karp would never choose this, then augment the graph with some more vertices between s and v and between u and t).

Without reversing flow u → v, it is impossible to obtain the optimal flow of 20.

Looming

BFS discovers shortest paths first (number of edges). It will grab the two 10 flow paths first, and the 1 weight edge won't be considered. I just ran my code with your graph and the max flow is indeed 20. – Arvie

@prakharsingh95 : I completely agree with the answer of Ami Tavory, it does not make sense to forget about back edges. – Ruth

Sorry, I was on mobile and somehow missed it. Indeed you are correct. In fact, @ead gave the same example. From what I understand, this means that when there is are longer paths with bigger net flow than a short path, which shares edges with them it becomes necessary to to add back edges. – Arvie

@DamienProt Yeah, back edges are important. I just couldn't figure out why! – Arvie

I might be crazy, but couldn't we collapse any series of nodes with one incoming and one outgoing into one node with the min of the set of the original edges? For ex: A - (5) -> B - (4) -> C - (5) -> D can be reduced to A - (4) -> D – Polity

Answer 2

try out the following case:

int main() {
    Digraph<int> g(8);
    g.addEdge(0,1,1);
    g.addEdge(1,2,1);
    g.addEdge(2,4,1);
    g.addEdge(0,3,1);
    g.addEdge(3,4,1);
    g.addEdge(4,7,1);
    g.addEdge(3,5,1);
    g.addEdge(5,6,1);
    g.addEdge(6,7,1);

    cout<<g.maxFlowEdmondsKarp(0,7);

    return 0;
}

Visualization:

your program takes the shortest way 0-3-4-7 first and has then no chance to find 0-1-2-4-7 and 0-3-5-6-7. You get 1 but 2 would be the right answer.

Would you have inserted the back-edge, then you would find the following paths:

1. 0-3-4-7
2. 0-1-2-4-3(back-edge!)-5-6-7, getting the max flow 2.

Dentiform