The Maximum Flow Problem and the Ford-Fulkerson Method

The maximum flow problem is a classic network flow problem. Imagine you have an oil pipeline network with a source (like a refinery) and a sink (like a port). The pipes have fixed capacities (the maximum flow rate per unit time). The problem is how to schedule the flow on each pipe so that the total flow from the source to the sink is maximized. The Ford-Fulkerson method is a fundamental and important framework for solving this problem.

I. Problem Description and Modeling

We abstract this pipeline network into a directed graph G=(V, E).

• V is the set of vertices (e.g., pipe junctions, stations).
• E is the set of edges (i.e., pipes).
• Each edge (u, v) ∈ E has a non-negative capacity c(u, v) ≥ 0. If the edge (u, v) does not exist, we set c(u, v) = 0.
• We designate two special vertices: the source s and the sink t.

A flow f is a function from V × V to real numbers that satisfies the following two key constraints:

1. Capacity Constraint: For all u, v ∈ V, 0 ≤ f(u, v) ≤ c(u, v). The flow on an edge cannot exceed its capacity.
2. Flow Conservation: For all u ∈ V - {s, t}, ∑_{v∈V} f(v, u) = ∑_{w∈V} f(u, w). That is, for any vertex other than the source and sink, the total flow entering the vertex must equal the total flow leaving the vertex (no storage or spontaneous generation).

The value |f| of a flow is defined as the net flow out of the source: |f| = ∑_{v∈V} f(s, v) - ∑_{v∈V} f(v, s). It is usually assumed that no edge enters the source, so |f| = ∑_{v∈V} f(s, v). Our goal is to find a flow f that maximizes its value |f|.

II. Core Ideas: Residual Network and Augmenting Paths

The essence of the Ford-Fulkerson method is iterative improvement. It starts from a zero flow (all edge flows are 0) and continuously finds paths where more flow can be "pushed."

1. Residual Capacity and Residual Network:
   Given graph G and the current flow f, for an edge (u, v), we define its residual capacity c_f(u, v) as how much more flow can be added on top of this current flow.

   • If the original edge (u, v) still has remaining capacity, i.e., f(u, v) < c(u, v), then c_f(u, v) = c(u, v) - f(u, v). This means we can push up to c_f(u, v) more flow along the direction of this edge.
   • Additionally, we need to consider the possibility of reversal. The current flow f(v, u) represents flow from v to u. This part of the flow can actually be canceled (or "reversed"). Therefore, we define a residual capacity for the reverse edge as c_f(v, u) = f(u, v).

   The graph G_f consisting of all vertices V and all edges where the residual capacity c_f(u, v) > 0 (including forward edges with remaining capacity and reverse edges for flow cancellation) is called the residual network. It precisely describes which paths can be used to increase flow given the current flow state.

2. Augmenting Paths:
   In the residual network G_f, any simple path p from the source s to the sink t is called an augmenting path.
   The bottleneck capacity c_f(p) of this path is defined as the minimum residual capacity among all edges on the path, i.e., c_f(p) = min{ c_f(u, v) | (u, v) is on path p }.
   Key Operation: We can "push" an additional flow of size c_f(p) along this augmenting path p. How does this operation affect the original flow f?

   • For each forward edge (u, v) on path p (i.e., an original edge in G), we increase its flow f(u, v) by c_f(p).
   • For each reverse edge (v, u) on path p (which corresponds to the original edge (u, v)), we effectively cancel some of the original flow from u to v, so we decrease f(u, v) by c_f(p).

   This operation always satisfies the capacity constraint and flow conservation. Intuitively, we find a path that can still carry flow and push through the maximum amount determined by the narrowest section (bottleneck). The existence of reverse edges is crucial; it allows the algorithm to undo previous suboptimal flow assignments ("pushing back" flow from an edge), enabling it to find the global optimal solution.

III. Steps of the Ford-Fulkerson Algorithm

The algorithm procedure is very clear:

1. Initialize: For all edges (u, v) ∈ E, set f(u, v) = 0.
2. Loop:
   a. In the residual network G_f corresponding to the current flow f, use a graph search algorithm (like BFS or DFS) to find an augmenting path p from s to t.
   b. If no such path is found, the algorithm terminates; the current f is the maximum flow.
   c. If found, calculate the bottleneck capacity c_f(p) of this path.
   d. Update the flow f along path p: For each edge (u, v) on the path:
   * If (u, v) is a forward edge in E, then f(u, v) = f(u, v) + c_f(p).
   * If (u, v) is a reverse edge in the residual network (corresponding to the original edge (v, u)), then f(v, u) = f(v, u) - c_f(p).

IV. Example Demonstration

Consider a simple network, s is the source, t is the sink, edges and capacities are as follows:
s -> A (10), s -> B (5), A -> B (3), A -> t (7), B -> t (8)

• Iteration 1:
  • Initial flow f is all 0.
  • Residual network G_f is the same as the original graph (because all edges have residual capacity equal to original capacity, reverse edge capacities are 0 and not shown).
  • Find an augmenting path s -> A -> t, bottleneck capacity min(10, 7) = 7.
  • Update flow: f(s, A)=7, f(A, t)=7.
• Iteration 2:
  • Current flow: f(s,A)=7, f(A,t)=7, others are 0. Build the residual network:
    • Edge (s,A): remaining 10-7=3, forward edge s->A capacity 3; reverse edge A->s capacity f(s,A)=7.
    • Edge (A,t): remaining 7-7=0, forward edge disappears; reverse edge t->A capacity 7.
    • Edge (s,B): remaining 5, forward edge capacity 5.
    • Edge (A,B): remaining 3, forward edge capacity 3.
    • Edge (B,t): remaining 8, forward edge capacity 8.
  • Find augmenting path s -> B -> t, bottleneck capacity min(5, 8)=5.
  • Update flow: f(s,B)=5, f(B,t)=5.
• Iteration 3:
  • Current flow: f(s,A)=7, f(A,t)=7, f(s,B)=5, f(B,t)=5.
  • Build residual network (omitted). Can find augmenting path s -> A -> B -> t.
    • s->A residual capacity 3.
    • A->B residual capacity 3.
    • B->t residual capacity 8-5=3.
  • Bottleneck capacity min(3, 3, 3)=3.
  • Update flow:
    • f(s,A) = 7+3 = 10
    • f(A,B) = 0+3 = 3 (Note A->B is a forward edge)
    • f(B,t) = 5+3 = 8
    • Meanwhile, f(A,t) remains 7. Note flow conservation at B: inflow to B is f(A,B)=3 plus f(s,B)=5, total 8; outflow from B is f(B,t)=8. Conservation holds.
• Termination:
  • Flow value now |f| = f(s,A) + f(s,B) = 10 + 5 = 15.
  • In the final residual network, t is no longer reachable from s (e.g., s->A is saturated, s->B is saturated, and no other path leads to t). Algorithm terminates.
  • Final maximum flow is 15.

V. Key Theorems and Algorithm Analysis

• Max-Flow Min-Cut Theorem: This is the cornerstone theorem of network flow theory. It states that in a flow network, the value of the maximum flow from source s to sink t equals the minimum sum of the capacities of all edges going from a set S containing s to a set T containing t (this sum is called the capacity of an (S, T) cut). This theorem guarantees the correctness of the Ford-Fulkerson method—when no s-t path exists in the residual network, a cut can be constructed from the current flow whose capacity equals the current flow value, thereby proving the current flow is maximal.
• Time Complexity: The Ford-Fulkerson method itself is a framework; its time complexity depends on how augmenting paths are found.
  • If DFS is used to find paths and edge capacities are integers, each augmentation increases the flow value by at least 1. Let the maximum flow value be |f*|, then the algorithm takes O(|f*| * |E|) time. With large or non-integer capacities, it may not terminate in polynomial time.
  • Therefore, in practice, its improved version—the Edmonds-Karp algorithm—is often used, which specifies that BFS must be used to find augmenting paths (i.e., always finding the shortest s-t path). This guarantees the algorithm finishes in O(|V| * |E|^2) time, a deterministic polynomial-time algorithm. Each BFS path search is O(|E|), and the number of BFS searches can be proven not to exceed O(|V| * |E|).

VI. Summary

The Ford-Fulkerson method approaches the maximum flow by iteratively finding augmenting paths in the residual network and pushing flow along them. The introduction of reverse edges is key to the algorithm's ability to find the global optimum. When no path from s to t exists in the residual network, the algorithm terminates, and the current flow is the maximum flow. Its improved version, the Edmonds-Karp algorithm (using BFS to find augmenting paths), provides a stable polynomial time complexity guarantee.