Maximum flow problem

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 Network", 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 formula_1 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 formula_2 for the minimum-cost flow problem of which for the maximum flow problem is a particular case. For the single-source shortest path (SSSP) problem with negative weights another particular case of minimum-cost flow problem an algorithm in almost-linear time has also been reported. Both algorithms were deemed best papers at the 2022 Symposium on Foundations of Computer Science.
Definition.
First we establish some notation:
Definition. The capacity of an edge is the maximum amount of flow that can pass through an edge. Formally it is a map formula_11
Definition. A flow is a map formula_12 that satisfies the following:
"Remark". Flows are skew symmetric: formula_16 for all formula_14
Definition. The value of flow is the amount of flow passing from the source to the sink. Formally for a flow formula_18 it is given by:
Definition. The maximum flow problem is to route as much flow as possible from the source to the sink, in other words find the flow formula_20 with maximum value.
Note that several maximum flows may exist, and if arbitrary real (or even arbitrary rational) values of flow are permitted (instead of just integers), there is either exactly one maximum flow, or infinitely many, since there are infinitely many linear combinations of the base maximum flows. In other words, if we send formula_21 units of flow on edge formula_22 in one maximum flow, and formula_23 units of flow on formula_22 in another maximum flow, then for each formula_25 we can send formula_26 units on formula_22 and route the flow on remaining edges accordingly, to obtain another maximum flow. If flow values can be any real or rational numbers, then there are infinitely many such formula_28 values for each pair formula_29.
Algorithms.
The following table lists algorithms for solving the maximum flow problem.
Here, formula_30 and formula_31 denote the number of vertices and edges of the network.
The value formula_32 refers to the largest edge capacity after rescaling all capacities to integer values
(if the network contains irrational capacities, formula_32 may be infinite).
For additional algorithms, see .
Integral flow theorem.
The integral flow theorem states that
The claim is not only that the value of the flow is an integer, which follows directly from the max-flow min-cut theorem, but that the flow on "every edge" is integral. This is crucial for many combinatorial applications (see below), where the flow across an edge may encode whether the item corresponding to that edge is to be included in the set sought or not.
Application.
Multi-source multi-sink maximum flow problem.
Given a network formula_3 with a set of sources formula_35 and a set of sinks formula_36 instead of only one source and one sink, we are to find the maximum flow across formula_5. We can transform the multi-source multi-sink problem into a maximum flow problem by adding a "consolidated source" connecting to each vertex in formula_38 and a "consolidated sink "connected by each vertex in formula_39 (also known as "supersource" and "supersink") with infinite capacity on each edge (See Fig. 4.1.1.).
Maximum cardinality bipartite matching.
Given a bipartite graph formula_40, we are to find a maximum cardinality matching in formula_41, that is a matching that contains the largest possible number of edges. This problem can be transformed into a maximum flow problem by constructing a network formula_42, where
Then the value of the maximum flow in formula_5 is equal to the size of the maximum matching in formula_41, and a maximum cardinality matching can be found by taking those edges that have flow formula_55 in an integral max-flow.
Minimum path cover in directed acyclic graph.
Given a directed acyclic graph formula_56, we are to find the minimum number of vertex-disjoint paths to cover each vertex in formula_30. We can construct a bipartite graph formula_58 from formula_41, where
Then it can be shown that formula_63 has a matching formula_64 of size formula_65 if and only if formula_41 has a vertex-disjoint path cover formula_67 containing formula_65 edges and formula_69 paths, where formula_70 is the number of vertices in formula_41. Therefore, the problem can be solved by finding the maximum cardinality matching in formula_63 instead.
Assume we have found a matching formula_64 of formula_63, and constructed the cover formula_67 from it. Intuitively, if two vertices formula_76 are matched in formula_64, then the edge formula_78 is contained in formula_67. Clearly the number of edges in formula_67 is formula_65. To see that formula_67 is vertex-disjoint, consider the following:
Thus no vertex has two incoming or two outgoing edges in formula_67, which means all paths in formula_67 are vertex-disjoint.
To show that the cover formula_67 has size formula_69, we start with an empty cover and build it incrementally. To add a vertex formula_22 to the cover, we can either add it to an existing path, or create a new path of length zero starting at that vertex. The former case is applicable whenever either formula_8 and some path in the cover starts at formula_86, or formula_105 and some path ends at formula_86. The latter case is always applicable. In the former case, the total number of edges in the cover is increased by 1 and the number of paths stays the same; in the latter case the number of paths is increased and the number of edges stays the same. It is now clear that after covering all formula_70 vertices, the sum of the number of paths and edges in the cover is formula_70. Therefore, if the number of edges in the cover is formula_65, the number of paths is formula_69.
Maximum flow with vertex capacities.
Let formula_3 be a network. Suppose there is capacity at each node in addition to edge capacity, that is, a mapping formula_112 such that the flow formula_113 has to satisfy not only the capacity constraint and the conservation of flows, but also the vertex capacity constraint
In other words, the amount of flow passing through a vertex cannot exceed its capacity. To find the maximum flow across formula_5, we can transform the problem into the maximum flow problem in the original sense by expanding formula_5. First, each formula_117 is replaced by formula_118 and formula_119, where formula_118 is connected by edges going into formula_86 and formula_119 is connected to edges coming out from formula_86, then assign capacity formula_124 to the edge connecting formula_118 and formula_119 (see Fig. 4.4.1). In this expanded network, the vertex capacity constraint is removed and therefore the problem can be treated as the original maximum flow problem.
Maximum number of paths from s to t.
Given a directed graph formula_56 and two vertices formula_128 and formula_129, we are to find the maximum number of paths from formula_128 to formula_129. This problem has several variants:
1. The paths must be edge-disjoint. This problem can be transformed to a maximum flow problem by constructing a network formula_3 from formula_41, with formula_128 and formula_129 being the source and the sink of formula_5 respectively, and assigning each edge a capacity of formula_55. In this network, the maximum flow is formula_138 iff there are formula_138 edge-disjoint paths.
2. The paths must be independent, i.e., vertex-disjoint (except for formula_128 and formula_129). We can construct a network formula_3 from formula_41 with vertex capacities, where the capacities of all vertices and all edges are formula_55. Then the value of the maximum flow is equal to the maximum number of independent paths from formula_128 to formula_129.
3. In addition to the paths being edge-disjoint and/or vertex disjoint, the paths also have a length constraint: we count only paths whose length is exactly formula_138, or at most formula_138. Most variants of this problem are NP-complete, except for small values of formula_138.
Closure problem.
A closure of a directed graph is a set of vertices "C", such that no edges leave "C". The closure problem is the task of finding the maximum-weight or minimum-weight closure in a vertex-weighted directed graph. It may be solved in polynomial time using a reduction to the maximum flow problem.
Real world applications.
Baseball elimination.
In the baseball elimination problem there are "n" teams competing in a league. At a specific stage of the league season, "w""i" is the number of wins and "r""i" is the number of games left to play for team "i" and "r"ij is the number of games left against team "j". A team is eliminated if it has no chance to finish the season in the first place. The task of the baseball elimination problem is to determine which teams are eliminated at each point during the season. Schwartz proposed a method which reduces this problem to maximum network flow. In this method a network is created to determine whether team "k" is eliminated.
Let "G" = ("V", "E") be a network with being the source and the sink respectively. One adds a game node"ij" – which represents the number of plays between these two teams. We also add a team node for each team and connect each game node with "i" &lt; "j" to "V", and connects each of them from "s" by an edge with capacity "r""ij" – which represents the number of plays between these two teams. We also add a team node for each team and connect each game node with two team nodes "i" and "j" to ensure one of them wins. One does not need to restrict the flow value on these edges. Finally, edges are made from team node "i" to the sink node "t" and the capacity of is set to prevent team "i" from winning more than .
Let "S" be the set of all teams participating in the league and let 
In this method it is claimed team "k" is not eliminated if and only if a flow value of size "r"("S" − {"k"}) exists in network "G". In the mentioned article it is proved that this flow value is the maximum flow value from "s" to "t".
Airline scheduling.
In the airline industry a major problem is the scheduling of the flight crews. The airline scheduling problem can be considered as an application of extended maximum network flow. The input of this problem is a set of flights "F" which contains the information about where and when each flight departs and arrives. In one version of airline scheduling the goal is to produce a feasible schedule with at most "k" crews.
To solve this problem one uses a variation of the circulation problem called bounded circulation which is the generalization of network flow problems, with the added constraint of a lower bound on edge flows.
Let "G" = ("V", "E") be a network with as the source and the sink nodes. For the source and destination of every flight "i", one adds two nodes to "V", node "s""i" as the source and node "d""i" as the destination node of flight "i". One also adds the following edges to "E":
In the mentioned method, it is claimed and proved that finding a flow value of "k" in "G" between "s" and "t" is equal to finding a feasible schedule for flight set "F" with at most "k" crews.
Another version of airline scheduling is finding the minimum needed crews to perform all the flights. To find an answer to this problem, a bipartite graph is created where each flight has a copy in set "A" and set "B". If the same plane can perform flight "j" after flight "i", is connected to . A matching in induces a schedule for "F" and obviously maximum bipartite matching in this graph produces an airline schedule with minimum number of crews. As it is mentioned in the Application part of this article, the maximum cardinality bipartite matching is an application of maximum flow problem.
Circulation–demand problem.
There are some factories that produce goods and some villages where the goods have to be delivered. They are connected by a networks of roads with each road having a capacity for maximum goods that can flow through it. The problem is to find if there is a circulation that satisfies the demand.
This problem can be transformed into a maximum-flow problem.
Let "G" = ("V", "E") be this new network. There exists a circulation that satisfies the demand if and only if :
If there exists a circulation, looking at the max-flow solution would give the answer as to how much goods have to be sent on a particular road for satisfying the demands.
The problem can be extended by adding a lower bound on the flow on some edges.
Image segmentation.
In their book, Kleinberg and Tardos present an algorithm for segmenting an image. They present an algorithm to find the background and the foreground in an image. More precisely, the algorithm takes a bitmap as an input modelled as follows: "ai" ≥ 0 is the likelihood that pixel "i" belongs to the foreground, "bi" ≥ 0 in the likelihood that pixel "i" belongs to the background, and "pij" is the penalty if two adjacent pixels "i" and "j" are placed one in the foreground and the other in the background. The goal is to find a partition ("A", "B") of the set of pixels that maximize the following quantity
Indeed, for pixels in "A" (considered as the foreground), we gain "ai"; for all pixels in "B" (considered as the background), we gain "bi". On the border, between two adjacent pixels "i" and "j", we loose "pij". It is equivalent to minimize the quantity
because
We now construct the network whose nodes are the pixel, plus a source and a sink, see Figure on the right. We connect the source to pixel "i" by an edge of weight "ai". We connect the pixel "i" to the sink by an edge of weight "bi". We connect pixel "i" to pixel "j" with weight "pij". Now, it remains to compute a minimum cut in that network (or equivalently a maximum flow). The last figure shows a minimum cut.
Extensions.
1. In the minimum-cost flow problem, each edge ("u",v) also has a cost-coefficient "auv" in addition to its capacity. If the flow through the edge is "fuv", then the total cost is "auvfuv." It is required to find a flow of a given size "d", with the smallest cost. In most variants, the cost-coefficients may be either positive or negative. There are various polynomial-time algorithms for this problem.
2. The maximum-flow problem can be augmented by disjunctive constraints: a "negative disjunctive constraint" says that a certain pair of edges cannot simultaneously have a nonzero flow; a "positive disjunctive constraints" says that, in a certain pair of edges, at least one must have a nonzero flow. With negative constraints, the problem becomes strongly NP-hard even for simple networks. With positive constraints, the problem is polynomial if fractional flows are allowed, but may be strongly NP-hard when the flows must be integral.