16  Implementing Ford-Fulkerson and Running Time

This section discusses an implementation of Ford-Fulkerson called Edmonds-Karp and analyzes its running time.

Objectives. After learning this material, you should be able to:

• Implement the Edmonds-Karp algorithm on examples.
• Identify the time complexity of Edmonds-Karp.

16.1 Using Breadth-First Search

The part of Ford-Fulkerson that is not fully specified is how to choose a path from \(s\) to \(t\) in the residual graph, \(G_f\). We will simply use BFS. The resulting algorithm is called Edmonds-Karp.

Algorithm 16.1  

edmondskarp(G, c):
   # G is a directed graph, c is a capacity function
   let f(u,v) = 0 for all vertex pairs u,v
   repeat:
      let Gf and rf = residuals(G, c, f)
      use BFS to find a path from s to t in Gf  
      let f and d = augment(G, f, rf, path)
      if d == 0:
         return f

Because Edmonds-Karp is in the Ford-Fulkerson framework, we know that it is correct as long as it halts. We will show that it halts and give a bound on the number of time steps.

Proposition 16.1 On a graph with \(n\) vertices and \(m\) edges, Edmonds-Karp runs in time \(O(n m^2)\).

Proof (optional).

In a round of Edmonds-Karp, an edge is called critical if we augment along a path containing that edge, and the residual capacity is equal to the augmentation amount. In other words, that edge has the minimum residual capacity of any edge along the path.

Note that a critical edge is present in \(G_f\) in the current round, but disappears in the next round, because the edge’s capacity is fully saturated.

First, we show that in each round, a vertex’s distance from \(s\) in the residual graph \(G_f\) can only increase. (This is the unweighted distance, i.e. number of hops.) To see this, consider the change in the residual graph. When we augment along a path \(s=v_1,\dots,v_k=t\), we may add new reverse edges of the form \((v_j, v_{j-1})\) to \(G_f\), and we remove forward edges if they are critical edges. Because \(v_1,\dots,v_k\) is a shortest path from \(s\), adding reverse edges cannot make any paths shorter, since we would never go through \(v_{j+1}\) to get to \(v_j\). And eliminating edges cannot make any paths shorter.

Next, we show that each edge \((u,v)\) can only be critical in at most \(n/2\) iterations. When an edge is critical, it is removed from the residual graph by augmenting. To become critical again, it must be added back into the flow graph by augmenting along the reverse direction, \((v,u)\). But that implies the distance from \(s\) to \(u\) has increased by at least \(2\), since it was strictly less than the distance to \(v\), and now it’s strictly more, and the distance to \(v\) has not decreased. Since the distance begins at zero or more, and ends at \(n\) or less, and increases by at least \(2\) each round, the total number of times the edge is critical is at most \(n/2\).

Finally, we put the pieces together. There are up to \(2m\) potential edges in the residual graph: each edge in the original graph, and its reverse. Each can be critical at most \(n/2\) times, and every round there is at least one critical edge, so there are at most \((2m)(n/2) = mn\) iterations. In each iteration, we do a constant amount of work and run BFS, which takes \(O(m + n)\) time. We can assume that \(m \geq n-1\) here, as the graph can be assumed to be connected, so the running time of BFS is \(O(m)\). Putting it all together, we have a running time of \(O((mn)(m)) = O(n m^2)\).