In optimization theory, maximum flow problems involve finding a feasible flow through a flow network that obtains the maximum possible flow rate. The maximum flow problem can be seen as a special case of more complex network flow problems, such as the circulation problem. The maximum value of an s-t flow (i.e., flow from source s to sink t) is equal to the minimum capacity of an s-t cut (i.e., cut severing s from t) in the network, as stated in the max-flow min-cut theorem.
History The maximum flow 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, the Ford–Fulkerson algorithm. In their 1955 paper, Ford and Fulkerson wrote that the problem of Harris and Ross is formulated as follows (see p. 5):Consider a rail network connecting two cities by way of a number of intermediate cities, where each link of the network has a number assigned to it representing its capacity. Assuming a steady state condition, find a maximal flow from one given city to the other.In their book Flows in Networks, in 1962, Ford and Fulkerson wrote:It was posed to the authors in the spring of 1955 by T. E. Harris, who, in conjunction with General F. S. Ross (Ret.), had formulated a simplified model of railway traffic flow, and pinpointed this particular problem as the central one suggested by the model [11].where [11] refers to the 1955 secret report Fundamentals of a Method for Evaluating Rail net Capacities by Harris and Ross (see p. 5). Over the years, various improved solutions to the maximum flow problem were discovered, notably 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. The algorithms of Sherman and Kelner, Lee, Orecchia and Sidford, respectively, find an approximately optimal maximum flow but only work in undirected graphs. In 2013 James B. Orlin published a paper describing an O ( | V | | E | ) {\displaystyle O(|V||E|)} algorithm. In 2022 Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva published an almost-linear time algorithm running in O ( | E | 1 + o ( 1 ) ) {\displaystyle O(|E|^{1+o(1)})} for the minimum-cost flow problem of which the maximum flow problem is a particular case. For the single-source shortest path (SSSP) problem with negative weights – another particular case of a minimum-cost flow problem – an algorithm running in almost-linear time has also been reported. Both algorithms were deemed best papers at the 2022 Symposium on Foundations of Computer Science. A derandomized version of the 2022 algorithm by Chen et al was presented at the 2023 Symposium on Foundations of Computer Science, establishing that minimum-cost flow could be solved deterministically in almost-linear time.
Definition
First we establish some notation:
Let N = ( V , E ) {\displaystyle N=(V,E)} be a flow network with s , t ∈ V {\displaystyle s,t\in V} being the source and the sink of N {\displaystyle N} respectively. If g {\displaystyle g} is a function on the edges of N {\displaystyle N} then its value on ( u , v ) ∈ E {\displaystyle (u,v)\in E} is denoted by g u v {\displaystyle g_{uv}} or g ( u , v ) . {\displaystyle g(u,v).}
Definition. The capacity of an edge is the maximum amount of flow that can pass through an edge. Formally it is a map c : E → R + . {\displaystyle c:E\to \mathbb {R} ^{+}.}
Definition. A flow is a map f : E → R {\displaystyle f:E\to \mathbb {R} } that satisfies the following:
Capacity constraint. The flow of an edge cannot exceed its capacity, in other words: f u v ≤ c u v {\displaystyle f_{uv}\leq c_{uv}} for all ( u , v ) ∈ E . {\displaystyle (u,v)\in E.}
Conservation of flows. The sum of the flows entering a node must equal the sum of the flows exiting that node, except for the source and the sink. Or:
… excerpt ends here. Continue reading the full article.
