Home › Computer Science › Graph Theory › Network Flow

Network Flow & Max-Flow Min-Cut Theorem

📅 Updated: Oct 24, 2025 👤 Verified by Expert Editors ⏱️ 12 min read

In graph theory and operations research, a network flow models the movement of a commodity (data, vehicles, fluid, etc.) through a directed graph. The Max-Flow Min-Cut Theorem is a cornerstone result stating that the maximum amount of flow that can be sent from a source to a sink equals the minimum capacity of a cut that separates them.

Introduction

Network flow problems arise naturally in transportation, telecommunications, supply chain logistics, and computer science. At their core, they ask: "What is the maximum throughput possible through a network of constrained links?"

The Max-Flow Min-Cut Theorem, first proven by Ford and Fulkerson in 1956, elegantly connects two seemingly different concepts: the maximum flow that can traverse a network and the minimum capacity that, if removed, would disconnect the source from the sink. This duality is fundamental to combinatorial optimization.

Fundamentals of Network Flow

Definition: Flow Network

A flow network is a directed graph \(G = (V, E)\) with a distinguished source node \(s \in V\) and sink node \(t \in V\). Each edge \((u, v) \in E\) has a non-negative capacity \(c(u, v) \geq 0\). If \((u, v) \notin E\), then \(c(u, v) = 0\).

A flow is a real-valued function \(f: V \times V \to \mathbb{R}\) satisfying three properties:

  1. Capacity Constraint: \(0 \leq f(u, v) \leq c(u, v)\) for all \(u, v \in V\).
  2. Skew Symmetry: \(f(u, v) = -f(v, u)\).
  3. Flow Conservation: For all \(v \in V \setminus \{s, t\}\), \(\sum_{u \in V} f(u, v) = 0\).

The value of a flow \(|f|\) is defined as the net flow out of the source:

\(|f| = \sum_{v \in V} f(s, v)\)

Max-Flow Min-Cut Theorem

Definition: Cut

An \(s-t\) cut is a partition of vertices \(V\) into two disjoint sets \(S\) and \(T\) such that \(s \in S\) and \(t \in T\). The capacity of the cut is:

\(c(S, T) = \sum_{u \in S} \sum_{v \in T} c(u, v)\)
Theorem: Max-Flow Min-Cut

For any flow network \(G\), the following three statements are equivalent:

  1. The flow \(f\) is a maximum flow in \(G\).
  2. The residual graph \(G_f\) contains no augmenting paths from \(s\) to \(t\).
  3. The value of the flow \(|f|\) equals the capacity of a minimum \(s-t\) cut in \(G\).

In short: Maximum flow value = Minimum cut capacity.

Intuition: Imagine a water pipe system. The maximum amount of water you can pump from the source to the sink is limited by the narrowest bottleneck you can cut to stop all flow. The theorem proves these two quantities are always equal.

Algorithms

Several algorithms compute maximum flow by iteratively finding augmenting paths in the residual graph.

Algorithm: Ford-Fulkerson
  1. Initialize \(f(u,v) = 0\) for all edges.
  2. While there exists a path from \(s\) to \(t\) in the residual graph \(G_f\) with positive capacity:
  3. Find such a path \(P\) and let \(b_f(P)\) be the minimum residual capacity along \(P\).
  4. Augment flow along \(P\) by \(b_f(P)\): update \(f(u,v) \leftarrow f(u,v) + b_f(P)\) and \(f(v,u) \leftarrow f(v,u) - b_f(P)\).
  5. Return \(f\).

Time Complexity: \(O(|f^*| \cdot E)\), where \(|f^*|\) is the max flow value. Pseudopolynomial if capacities are integers.

Edmonds-Karp Algorithm: A specific implementation of Ford-Fulkerson that always selects the shortest augmenting path (by BFS). Guarantees \(O(V E^2)\) runtime regardless of capacity values.

Dinic's Algorithm: Uses blocking flows in level graphs (built via BFS) to achieve \(O(V^2 E)\) generally, and \(O(V^{4/3} E)\) for unit capacities. Dominates in practice for large networks.

Applications

References

  1. Ford, L. R., & Fulkerson, D. R. (1956). "Maximal Flow through a Network". Canadian Journal of Mathematics, 8, 399–404.
  2. Edmonds, J., & Karp, R. M. (1972). "Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems". JACM, 19(2), 248–264.
  3. Dinic, E. A. (1970). "Algorithm for solution of a problem of maximum flow in a network with power estimation". PMME, 11(5), 127–130.
  4. Thomas H. Cormen et al. Introduction to Algorithms, 4th ed. MIT Press, 2022. Chapter 26: Maximum Flow.
  5. Aevum Encyclopedia Editorial Board. "Flow Networks and Combinatorial Optimization". Aevum Encyclopedia, 2025.