Maximum Flow: Ford-Fulkerson and the Min-Cut Max-Flow Theorem

What a Flow Network Represents

A Flow Network is a directed graph, as introduced earlier in this series, where each edge has a Capacity limiting how much "flow" can pass through it, and two designated vertices: a Source s where flow originates, and a Sink t where flow terminates. This models real scenarios like water flowing through pipes with limited diameter, data flowing through network links with limited bandwidth, or goods flowing through a supply chain with limited shipping capacity.

A valid flow must satisfy two properties:

Capacity Constraint: for every edge (u, v),
  the flow f(u,v) cannot exceed its capacity c(u,v)

Flow Conservation: for every vertex except s and t,
  total flow entering the vertex equals
  total flow leaving the vertex
  (flow cannot accumulate anywhere except source and sink)

The Maximum Flow Problem asks for the assignment of flow values to every edge that maximizes the total flow leaving the source (equivalently, the total flow arriving at the sink), while respecting both constraints above.

The Ford-Fulkerson Method: Repeatedly Finding Augmenting Paths

The Ford-Fulkerson Method is based on a simple, intuitive idea: as long as there exists a path from source to sink along which more flow could still be pushed, push additional flow along that path, and repeat until no such path remains.

The Residual Graph

The key structural idea that makes this method work correctly is the Residual Graph, which represents how much additional flow could still be pushed along each edge, and crucially, also represents the ability to "undo" flow already sent, through a reverse edge.

For an edge (u, v) with capacity c and current flow f:
Residual capacity forward: c(u,v) - f(u,v)
                            (remaining room to push more flow)
Residual capacity backward: f(u,v)
                            (ability to cancel flow already sent)

This reverse-edge mechanism is essential: it allows the algorithm to correct an earlier suboptimal choice by effectively "returning" flow along a path and rerouting it elsewhere, without which the algorithm could get stuck at a suboptimal solution.

The Algorithm

FORD-FULKERSON(G, s, t):
  initialize flow f to 0 on every edge
  while there exists a path p from s to t in the residual graph Gf:
      find the minimum residual capacity along p, call it cf(p)
      // this is the "bottleneck" of the augmenting path
      for each edge (u, v) in path p:
          if (u, v) is a forward edge:
              f(u, v) = f(u, v) + cf(p)
          else:      // (u, v) is a backward edge
              f(v, u) = f(v, u) - cf(p)
  return f

Each such path found in the residual graph is called an Augmenting Path, and pushing flow along it strictly increases the total flow by the path's bottleneck capacity — the smallest residual capacity among all edges on that path, since that edge limits how much additional flow the entire path can carry.

Tracing a Small Example

Simple network: s → a (cap 10), s → b (cap 10)
                a → t (cap 10), b → t (cap 10)
                a → b (cap 1)

Iteration 1: augmenting path s→a→t, bottleneck = 10
             Flow: s→a=10, a→t=10, total flow so far = 10

Iteration 2: augmenting path s→b→t, bottleneck = 10
             Flow: s→b=10, b→t=10, total flow so far = 20

No more augmenting paths exist (both a→t and b→t saturated)
Maximum flow = 20

Analyzing Running Time: Edmonds-Karp's Improvement

The basic Ford-Fulkerson method's running time depends on how augmenting paths are chosen, and with poor choices (and irrational capacities), it may not even terminate in a finite number of steps in pathological cases. The Edmonds-Karp Algorithm fixes this by specifically choosing the shortest augmenting path each time, found using breadth-first search, discussed earlier in this series.

Using BFS to find the shortest augmenting path
each iteration guarantees the algorithm terminates
in a bounded number of iterations:

Total running time: O(VE²)

This is because each edge can become the bottleneck
of a shortest augmenting path only O(V) times before
the shortest path length must strictly increase,
and there are only O(V) possible path lengths

This specific choice of augmenting path guarantees polynomial running time, in contrast to the unbounded or exponential behavior possible with an arbitrary path-selection strategy in the original Ford-Fulkerson method.

The Min-Cut Max-Flow Theorem

One of the most elegant results in combinatorial optimization connects the maximum flow problem to a seemingly unrelated one. An s-t Cut partitions the vertices into two sets, one containing s and the other containing t, similar to the cut concept discussed earlier in this series regarding minimum spanning trees. The Capacity of a cut is the sum of capacities of edges crossing from the source's side to the sink's side.

Min-Cut Max-Flow Theorem:
The maximum flow from s to t equals the minimum
capacity among all possible s-t cuts

max flow(s, t) = min cut capacity(s, t)

Intuitively, this makes sense: any cut's capacity represents an upper bound on how much flow can possibly cross from source to sink, since all flow must pass through the edges crossing that cut. The theorem's surprising and powerful claim is that this bound is always achievable exactly — the maximum flow always equals the tightest such bound, with no gap between them.

A direct consequence of this theorem is that when Ford-Fulkerson terminates (no augmenting path remains in the residual graph), the set of vertices still reachable from s in the residual graph, versus those that are not, defines a minimum cut whose capacity exactly equals the maximum flow just computed — providing both the maximum flow value and a certificate proving its optimality, simultaneously.

Why Maximum Flow Has Such Broad Applications

Beyond literal flow problems like water and traffic networks, maximum flow algorithms solve a surprising range of problems through clever graph modeling: bipartite matching (assigning workers to jobs, or students to schools, discussed further in problems adjacent to this one), image segmentation in computer vision, airline crew scheduling, and project selection problems in operations research. The fact that a problem can be reformulated as a maximum flow computation is often the key insight that transforms an apparently difficult combinatorial optimization problem into one solvable in polynomial time using the algorithms described in this article.