Network flow concepts (max flow intro)

The study of network flows originated not in a mathematics department, but in the context of Cold War logistics and military planning. During the 1950s, the United States Air Force sought to determine the maximum capacity at which supplies could be shipped through the Soviet railway network — and, conversely, the minimum set of links whose destruction would sever that capacity entirely. This practical question gave rise to one of the most elegant and widely applicable frameworks in combinatorial optimization, connecting graph theory, linear programming, and algorithm design in a single coherent structure.

The foundational result, the Max-Flow Min-Cut Theorem, was proved independently by multiple researchers and revealed a deep duality: the maximum amount of flow that can be pushed through a network equals the minimum capacity that must be removed to disconnect the source from the sink. This insight transformed operations research, telecommunications, and eventually computer science, where network flow algorithms underpin everything from image segmentation to bipartite matching.

The central question that the maximum flow framework addresses is deceptively simple: given a directed graph with edge capacities, a designated source vertex, and a designated sink vertex, what is the greatest total rate of flow that can be routed from source to sink while respecting every edge's capacity constraint? As we will see, answering this question requires a careful interplay between local decisions at individual edges and global structure across the entire network.

A flow network is a directed graph G = (V, E) equipped with a non-negative capacity function c : E → ℝ_≥0 and two distinguished vertices: a source s (which only emits flow) and a sink t (which only absorbs flow). The capacity c(u, v) on each edge (u, v) represents the upper bound on the rate at which material — data packets, fluid, goods — can traverse that link. If an edge (u, v) is not in E, we define c(u, v) = 0 by convention.

The following diagram depicts a flow network with source s and sink t. Each directed edge is labeled with the notation f / c where f denotes the current flow and c denotes the edge capacity. The coloring indicates how saturated each edge is: fully used edges appear in red, partially used edges in amber, and unused capacity edges in cyan.

Observe that the edge s → A is fully saturated at 10/10, meaning no additional flow can be pushed along it directly. However, the edge A → D carries only 4 of its 9 available capacity, and C → D is completely unused at 0/7. The existence of these slack edges suggests that there may be alternative routes through which additional flow could reach t. The residual graph formalizes this intuition by introducing reverse edges that permit the rerouting of previously assigned flow, opening up new augmenting paths that were invisible in the original network.

We now formalize the definitions introduced above. Let G = (V, E) be a directed graph with capacity function c and distinguished vertices s, t ∈ V. A flow in G is a function f : V × V → ℝ satisfying two properties: the capacity constraint and flow conservation. From these two simple axioms, the entire theory unfolds.

A crucial structural concept is an s–t cut (S, T), which is a partition of V into two disjoint sets S and T with s ∈ S and t ∈ T. The capacity of this cut is c(S, T) = ∑ c(u, v) over all edges with u ∈ S, v ∈ T. The Max-Flow Min-Cut Theorem states that the maximum value of any s–t flow equals the minimum capacity of any s–t cut. This duality is both theoretically profound — it connects to LP duality — and computationally useful, as it provides a certificate of optimality: once we exhibit a flow and a cut of equal value, both are optimal.

The Ford–Fulkerson method is the canonical algorithm for computing maximum flows. It is technically a method rather than an algorithm because it does not specify how to find augmenting paths — that choice yields different algorithmic variants with different time complexities. The procedure is elegant: start with zero flow on all edges, repeatedly find an augmenting path from s to t in the residual graph, push the maximum possible flow along that path (the bottleneck capacity), update the residual graph, and repeat until no augmenting path exists.

1. Initialize: Set f(u, v) = 0 for all edges. Construct the residual graph G_f = G (since all capacity is residual).
2. Search: Find any s–t path P in G_f. If none exists, terminate — the current flow is maximum.
3. Augment: Compute the bottleneck Δ = min c_f(u, v) over all edges (u, v) on P. Push Δ units along P.
4. Update: For each forward edge on P, decrease its residual capacity by Δ and increase the reverse edge by Δ. Return to Search.

The reverse edges in the residual graph are the key insight that makes the Ford–Fulkerson method correct. Without them, a greedy first choice could permanently block the optimal solution. Consider a scenario where an early augmenting path uses an edge that would have been more valuable on a different route. The reverse edge in G_f effectively allows a later iteration to "undo" that assignment by routing flow backward along the reverse edge, thereby rerouting the original flow to a more productive path. This self-correcting mechanism guarantees that the method converges to the true maximum flow regardless of the order in which augmenting paths are selected — provided, in the case of irrational capacities, that an appropriate path selection strategy (such as BFS) is used.

Consider a simple flow network with vertices {s, A, B, t} and edges: s → A (capacity 10), s → B (capacity 5), A → B (capacity 4), A → t (capacity 7), B → t (capacity 10). We apply the Ford–Fulkerson method to find the maximum flow from s to t.

The Ford–Fulkerson method is a template, and its efficiency depends critically on the strategy used to select augmenting paths. Different choices yield algorithms with vastly different worst-case time complexities. The table below compares the most important variants, their path selection strategies, and their computational guarantees.

The maximum flow problem sits at the heart of combinatorial optimization and connects to a remarkably wide array of more advanced topics. Understanding max flow provides the conceptual scaffolding for problems in matching, covering, scheduling, and even machine learning. The table below highlights several important generalizations and the role max flow plays in each.

Looking forward, recent breakthroughs have achieved nearly linear time algorithms for maximum flow in general graphs, combining techniques from continuous optimization (interior point methods), graph sparsification, and data structures for dynamic trees. These results, published by Chen et al. (2022), represent a culmination of decades of research and demonstrate that the simple question posed by Ford and Fulkerson in the 1950s continues to drive frontier research in theoretical computer science. For the student of discrete mathematics, mastering the basics of network flow provides both a powerful algorithmic toolkit and an entry point into the deep structural theory of graphs and optimization.