Maximum flow problem
Problem of maximizing flow through a network from source to sink.
The maximum flow problem is a foundational concept in optimization theory, concerned with finding the feasible flow through a flow network that achieves the highest possible flow rate from a source to a sink. The problem can be viewed as a specific instance of more complex network flow problems, such as the circulation problem. A central result is the max-flow min-cut theorem, which establishes that the maximum value of a flow from source to sink is equal to the minimum capacity of a cut separating the source from the sink.
The problem was first formulated in 1954 by T. E. Harris and General F. S. Ross as a simplified model of Soviet railway traffic flow. In 1955, Lester R. Ford, Jr. and Delbert R. Fulkerson created the first known algorithm to solve it, now called the Ford–Fulkerson algorithm. In their 1955 paper, they described the problem as finding a maximal flow from one given city to another in a rail network where each link has a capacity, assuming a steady state. In their 1962 book *Flows in Networks*, they noted that Harris had posed the problem to them in spring 1955, identifying it as the central issue suggested by the railway model.
Subsequent decades saw the development of many improved algorithms. Notable examples include the shortest augmenting path algorithm by Edmonds and Karp (and independently Dinitz), Dinitz’s blocking flow algorithm, the push-relabel algorithm by Goldberg and Tarjan, and the binary blocking flow algorithm by Goldberg and Rao. Some algorithms, such as those by Sherman and by Kelner, Lee, Orecchia, and Sidford, find an approximately optimal maximum flow but are restricted to undirected graphs. In 2013, James B. Orlin published an algorithm with a specific complexity bound. In 2022, Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva published an almost-linear time algorithm for the minimum-cost flow problem, of which the maximum flow problem is a particular case. Both this algorithm and an almost-linear time algorithm for the single-source shortest path problem with negative weights (another special case of minimum-cost flow) were recognized as best papers at the 2022 Symposium on Foundations of Computer Science. A derandomized version of the 2022 algorithm was presented at the 2023 Symposium, showing that minimum-cost flow could be solved deterministically in almost-linear
- field
- Optimization theory, network flow
- known_for
- Maximum flow problem, max-flow min-cut theorem
Lore & Background
The maximum flow problem is a foundational concept in optimization theory, concerned with finding a feasible flow through a flow network that achieves the highest possible flow rate. It can be considered a special case of more complex network flow problems, such as the circulation problem. A defining characteristic is the max-flow min-cut theorem, which states that the maximum value of a flow from a source to a sink is equal to the minimum capacity of a cut that separates the source from the sink. The problem was first formulated in 1954 by T. E. Harris and F. S. Ross as a simplified model of Soviet railway traffic flow. In 1955, Lester R. Ford, Jr. and Delbert R. Fulkerson created the first known algorithm for solving it, the Ford–Fulkerson algorithm. They noted that the problem was posed to them by Harris, who, with General F. S. Ross, had developed this railway model and identified the maximum flow problem as central. Over time, improved solutions emerged, including the shortest augmenting path algorithm, the blocking flow algorithm, the push-relabel algorithm, and the binary blocking flow algorithm. Some algorithms find an approximately optimal maximum flow but only work on undirected graphs. In 2013, James B. Orlin published a paper describing an algorithm. In 2022, an almost-linear time algorithm for the minimum-cost flow problem, of which maximum flow is a particular case, was published and deemed a best paper at the Symposium on Foundations of Computer Science; a derandomized version followed in 2023. The problem is formally defined on a flow network with a source and sink, where each edge has a capacity representing the maximum flow it can carry. A flow must satisfy capacity constraints and conservation of flows at all nodes except the source and sink. The value of a flow is the amount passing from source to sink, and the objective is to find a flow with the maximum possible value.
Reader's Guide
The maximum flow problem is a cornerstone of network flow theory, with the max-flow min-cut theorem providing a deep duality between flow and cut capacities. Over the years, improved solutions emerged, including the shortest augmenting path algorithm of Edmonds and Karp and independently Dinitz; the blocking flow algorithm of Dinitz; the push-relabel algorithm of Goldberg and Tarjan; and the binary blocking flow algorithm of Goldberg and Rao. Algorithms by Sherman and Kelner, Lee, Orecchia and Sidford find approximately optimal maximum flow but only work in undirected graphs. Orlin published an O(|V||E|) algorithm.
Did You Know?
- The max-flow min-cut theorem states that the maximum value of an s-t flow equals the minimum capacity of an s-t cut.
Frequently Asked Questions
What are Maximum flow problem's powers/role?
Its core ability is to determine the highest possible flow rate that can be routed through a directed graph from source to sink while respecting every edge's capacity constraint. In practice, it underpins everything from internet routing to airline scheduling and bipartite matching.
How does Maximum flow problem's story end?
Every episode resolves with the max-flow min-cut theorem, which guarantees that the largest achievable s-t flow is exactly equal to the smallest capacity s-t cut in the network. This duality means you can certify optimality simply by identifying that bottleneck cut.
More in Algorithms And Data Structures 1-24
Spotted an error? Know more?
This is a living reference — every entry is fact-audited, and reader corrections feed straight into our audit queue. Suggest an edit · See this site's audit record