How Does the Ford-Fulkerson Method Compute Maximum Flow?

The Ford-Fulkerson method computes the maximum flow from a source to a sink in a flow network by repeatedly finding augmenting paths in a residual graph and pushing additional flow along them until no more augmenting paths exist. By maintaining backward residual edges that allow previously assigned flow to be redirected, the algorithm guarantees that greedy path choices can be corrected to reach the global optimum.

Flow Networks and the Maximum Flow Problem

A flow network is a directed graph \(G = (V, E)\) with a designated source vertex \(s \in V\), a sink vertex \(t \in V\), and a non-negative capacity \(c(u, v) \ge 0\) for each edge \((u, v) \in E\). A valid flow is a function \(f: V \times V \to \mathbb{R}\) that satisfies two conditions:

Capacity constraint: For every edge \((u, v) \in E\), the flow cannot exceed the capacity, so \(0 \le f(u, v) \le c(u, v)\).
Flow conservation: For every vertex \(u \in V \setminus \{s, t\}\), the total incoming flow equals the total outgoing flow: \[\sum_{v \in V} f(v, u) = \sum_{v \in V} f(u, v)\]

The value of a flow, denoted \(|f|\), is the net flow leaving the source \(s\). The maximum flow problem seeks to maximize \(|f|\).

The Residual Graph

The central mechanism of the Ford-Fulkerson method is the residual graph \(G_f = (V, E_f)\), which represents how much additional flow can be pushed through the network given the current flow \(f\). For every pair of vertices \((u, v)\), the residual capacity \(c_f(u, v)\) is defined as:

\[c_f(u, v) = c(u, v) - f(u, v) + f(v, u)\]

In practice, this creates two types of edges in \(G_f\) for each original edge \((u, v) \in E\):

Forward edges: If \(f(u, v) < c(u, v)\), there is a residual capacity of \(c(u, v) - f(u, v)\) available to send more flow from \(u\) to \(v\).
Backward edges: If \(f(u, v) > 0\), there is a residual edge \((v, u)\) with capacity \(f(u, v)\). Pushing flow along this backward edge effectively cancels or redirects previously routed flow from \(u\) to \(v\).

Backward edges are essential because a greedy choice of paths early in the algorithm might block a better overall routing. The residual graph allows the algorithm to undo suboptimal decisions.

Augmenting Paths and Bottleneck Capacity

An augmenting path \(p\) is a simple path from the source \(s\) to the sink \(t\) in the residual graph \(G_f\) where every edge along \(p\) has strictly positive residual capacity. The maximum amount of additional flow that can be pushed along \(p\) is its bottleneck capacity, \(c_f(p)\), defined as the minimum residual capacity among all edges in the path:

\[c_f(p) = \min_{(u, v) \in p} c_f(u, v)\]

When the algorithm augments flow along \(p\), it updates the flow on each edge \((u, v) \in p\):

If \((u, v)\) is a forward edge, \(f(u, v)\) increases by \(c_f(p)\).
If \((u, v)\) is a backward edge, \(f(v, u)\) decreases by \(c_f(p)\).

After updating the flow, the residual graph \(G_f\) is recomputed, and the total flow value \(|f|\) increases by \(c_f(p)\).

Termination and the Max-Flow Min-Cut Theorem

The Ford-Fulkerson method repeats the search-and-augment loop until no augmenting path from \(s\) to \(t\) exists in \(G_f\). By the Max-Flow Min-Cut Theorem, when no augmenting path remains in the residual graph, the current flow \(f\) is guaranteed to be a maximum flow. At termination, the vertices reachable from \(s\) in \(G_f\) form one side of a minimum \(s\)-\(t\) cut whose capacity equals \(|f|\).

Time Complexity and Path Selection

Ford-Fulkerson is a method rather than a single fixed algorithm because it does not specify how to find the augmenting path. If capacities are integers, each augmentation increases the flow by at least \(1\), leading to a worst-case time complexity of \(O(E \cdot |f^*|)\), where \(|f^*|\) is the maximum flow value.

Using a breadth-first search to always select the shortest augmenting path (measured in number of edges) yields the Edmonds-Karp algorithm, which runs in \(O(V E^2)\) time independent of capacity values.