Network Flow: Ford-Fulkerson Method

Basic method (framework) is Ford-Fulkerson. It’s called a “method” because it’s general, there can be different implementation that yield different complexity. It looks like this:

Let F be an empty flow
While there is augmenting path P from s to t
    Augment F with P
End while

The problem is how we find the augmenting path efficiently. A naive implementation is to use DFS to randomly pick a $s-t$ path and augment it. However, it has two problems:

1. The algorithm may not terminate, this happens when the capacity is irrational number (we can always scale rational to integer). When the capacity is irrational, the flow may fluctuate and never converge.
2. Even when the capacity is integer, the algorithm may be too slow. The runtime depends on the size of flow \(\vert F\vert\), which means if \(\vert F\vert\) is large, it takes a long time to stop. To see this, note that DFS takes \(\vert E\vert\) time, in the worst case, \(F\) may grow by 1 at each iteration (since capacity is integer). Thus, the complexity is \(O(\vert E\vert F\vert )\).

To handle, this, Edmonds-Karp algorithm simply replaces the DFS as BFS, which finds a shortest each time (use unit length on edges in the residual graph). The major points are:

• The length shortest path is guaranteed to monotonically increase at each iteration. This can be proven by contradiction.
• The number of iterations are \(O(\vert V\vert E\vert )\).
  • Each augmenting path (shortest path) can saturate one edge, and this edge will disappear from the residual graph. We call this edge ‘critical’.
  • An edge \((u, v)\) becomes critical to the time when it next becomes critical, the distance to \(u\) from the source increases by at least 2.
  • Thus, the total number of critical edges during execution is \(O(\vert V\vert E\vert )\).
  • Each augmenting path contains at least one critical edge, thus \(O(\vert V\vert E\vert )\).
• The running time is thus \(O(\vert V\vert E\vert ^2)\) since each iteration we run a BFS which costs \(O(\vert E\vert )\). This can be improved to \(O(\vert V\vert ^2\vert E\vert )\) with more efficient data structure (Dinic).