Maximum flow problem

Definition

First we establish some notation:

• Let ${\displaystyle N=(V,E)}$ be a flow network with ${\displaystyle s,t\in V}$ being the source and the sink of ${\displaystyle N}$ respectively.
• If ${\displaystyle g}$ is a function on the edges of ${\displaystyle N}$ then its value on ${\displaystyle (u,v)\in E}$ is denoted by ${\displaystyle g_{uv}}$ or ${\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 ${\displaystyle c:E\to {\mathbb{R}}^{+}.}$

Definition. A flow is a map ${\displaystyle f:E\to \mathbb{R}}$ that satisfies the following:

• Capacity constraint. The flow of an edge cannot exceed its capacity, in other words: ${\displaystyle f_{uv}\le c_{uv}}$ for all ${\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:

${\displaystyle \mathrm{\forall }v\in V\setminus \{s,t\}:\sum _{u:(u,v)\in E,f_{uv}>0}{f}_{uv}=\sum _{u:(v,u)\in E,f_{vu}>0}{f}_{vu}.}$

Remark. Flows are skew symmetric: ${\displaystyle f_{uv}=-f_{vu}}$ for all ${\displaystyle (u,v)\in E.}$

Definition. The value of flow is the amount of flow passing from the source to the sink. Formally for a flow ${\displaystyle f:E\to {\mathbb{R}}^{+}}$ it is given by:

${\displaystyle |f|=\sum _{v:(s,v)\in E}{f}_{sv}=\sum _{u:(u,t)\in E}{f}_{ut}.}$

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 ${\displaystyle f_{\text{max}}}$ 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 ${\displaystyle x}$ units of flow on edge ${\displaystyle u}$ in one maximum flow, and ${\displaystyle y>x}$ units of flow on ${\displaystyle u}$ in another maximum flow, then for each ${\displaystyle \mathrm{\Delta }\in [0,y-x]}$ we can send ${\displaystyle x+\mathrm{\Delta }}$ units on ${\displaystyle u}$ 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 ${\displaystyle \mathrm{\Delta }}$ values for each pair ${\displaystyle x,y}$.

Algorithms

The following tables show the historical development of algorithms for solving the maximum flow problem. Many of the listed publications include similar tables comparing their results to earlier works.

Strongly polynomial

A strongly-polynomial time algorithm has polynomial time bounds that depend only on the number of inputs, but do not depend on the magnitude of these numbers. Here, the inputs are the vertices (numbered below as ${\displaystyle V}$) and edges (numbered as ${\displaystyle E}$). The complexity of each algorithm is stated using big O notation.

Pseudo-polynomial and weakly polynomial

In parallel to the development of strongly-polynomial flow algorithms, there has been a long line of pseudo-polynomial and weakly polynomial time bounds, whose running time depends on the magnitude of the input capacities. Here, the value ${\displaystyle U}$ refers to the largest edge capacity after rescaling all capacities to integer values. (If the network contains irrational capacities, this rescaling may not be possible and these algorithms may not produce exact solutions or may fail to converge even to an approximate solution). If some edges have infinite capacities, then ${\displaystyle U}$ can be taken as the largest finite capacity (more generally, ${\displaystyle U}$ is the largest capacity of an edge that can become saturated). The difference between pseudo-polynomial and weakly polynomial is that a pseudo-polynomial bound may be polynomial in ${\displaystyle U}$, but for a weakly polynomial bound it can be polynomial only in ${\displaystyle \log U}$.

Integral flow theorem

The integral flow theorem states that

If each edge in a flow network has integral capacity, then there exists an integral maximal flow.

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 ${\displaystyle N=(V,E)}$ with a set of sources ${\displaystyle S=\{s_1,\dots ,s_n\}}$ and a set of sinks ${\displaystyle T=\{t_1,\dots ,t_m\}}$ instead of only one source and one sink, we are to find the maximum flow across ${\displaystyle N}$. We can transform the multi-source multi-sink problem into a maximum flow problem by adding a consolidated source connecting to each vertex in ${\displaystyle S}$ and a consolidated sink connected by each vertex in ${\displaystyle T}$ (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 ${\displaystyle G=(X\cup Y,E)}$, we are to find a maximum cardinality matching in ${\displaystyle G}$, 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 ${\displaystyle N=(X\cup Y\cup \{s,t\},E^{\prime })}$, where

1. ${\displaystyle E^{\prime }}$ contains the edges in ${\displaystyle G}$ directed from ${\displaystyle X}$ to ${\displaystyle Y}$.
2. ${\displaystyle (s,x)\in E^{\prime }}$ for each ${\displaystyle x\in X}$ and ${\displaystyle (y,t)\in E^{\prime }}$ for each ${\displaystyle y\in Y}$.
3. ${\displaystyle c(e)=1}$ for each ${\displaystyle e\in E^{\prime }}$ (See Fig. 4.3.1).

Then the value of the maximum flow in ${\displaystyle N}$ is equal to the size of the maximum matching in ${\displaystyle G}$, and a maximum cardinality matching can be found by taking those edges that have flow ${\displaystyle 1}$ in an integral max-flow.

Minimum path cover in directed acyclic graph

Given a directed acyclic graph ${\displaystyle G=(V,E)}$, we are to find the minimum number of vertex-disjoint paths to cover each vertex in ${\displaystyle V}$. We can construct a bipartite graph ${\displaystyle G^{\prime }=(V_{\text{out}}\cup V_{\text{in}},E^{\prime })}$ from ${\displaystyle G}$, where

1. ${\displaystyle V_{\text{out}}=\{v_{\text{out}}\mid v\in V\wedge v\text{ has outgoing edge(s)}\}}$
2. ${\displaystyle V_{\text{in}}=\{v_{\text{in}}\mid v\in V\wedge v\text{ has incoming edge(s)}\}}$
3. ${\displaystyle E^{\prime }=\{(u_{\text{out}},v_{\text{in}})\in V_{out}\times V_{in}\mid (u,v)\in E\}}$.

Then it can be shown that ${\displaystyle G^{\prime }}$ has a matching ${\displaystyle M}$ of size ${\displaystyle m}$ if and only if ${\displaystyle G}$ has a vertex-disjoint path cover ${\displaystyle C}$ containing ${\displaystyle m}$ edges and ${\displaystyle n-m}$ paths, where ${\displaystyle n}$ is the number of vertices in ${\displaystyle G}$. Therefore, the problem can be solved by finding the maximum cardinality matching in ${\displaystyle G^{\prime }}$ instead.

Assume we have found a matching ${\displaystyle M}$ of ${\displaystyle G^{\prime }}$, and constructed the cover ${\displaystyle C}$ from it. Intuitively, if two vertices ${\displaystyle u_{\mathrm{o}\mathrm{u}\mathrm{t}},v_{\mathrm{i}\mathrm{n}}}$ are matched in ${\displaystyle M}$, then the edge ${\displaystyle (u,v)}$ is contained in ${\displaystyle C}$. Clearly the number of edges in ${\displaystyle C}$ is ${\displaystyle m}$. To see that ${\displaystyle C}$ is vertex-disjoint, consider the following:

1. Each vertex ${\displaystyle v_{\text{out}}}$ in ${\displaystyle G^{\prime }}$ can either be non-matched in ${\displaystyle M}$, in which case there are no edges leaving ${\displaystyle v}$ in ${\displaystyle C}$; or it can be matched, in which case there is exactly one edge leaving ${\displaystyle v}$ in ${\displaystyle C}$. In either case, no more than one edge leaves any vertex ${\displaystyle v}$ in ${\displaystyle C}$.
2. Similarly for each vertex ${\displaystyle v_{\text{in}}}$ in ${\displaystyle G^{\prime }}$ – if it is matched, there is a single incoming edge into ${\displaystyle v}$ in ${\displaystyle C}$; otherwise ${\displaystyle v}$ has no incoming edges in ${\displaystyle C}$.

Thus no vertex has two incoming or two outgoing edges in ${\displaystyle C}$, which means all paths in ${\displaystyle C}$ are vertex-disjoint.

To show that the cover ${\displaystyle C}$ has size ${\displaystyle n-m}$, we start with an empty cover and build it incrementally. To add a vertex ${\displaystyle u}$ 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 ${\displaystyle (u,v)\in E}$ and some path in the cover starts at ${\displaystyle v}$, or ${\displaystyle (v,u)\in E}$ and some path ends at ${\displaystyle v}$. 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 ${\displaystyle n}$ vertices, the sum of the number of paths and edges in the cover is ${\displaystyle n}$. Therefore, if the number of edges in the cover is ${\displaystyle m}$, the number of paths is ${\displaystyle n-m}$.

Maximum flow with vertex capacities

Let ${\displaystyle N=(V,E)}$ be a network. Suppose there is capacity at each node in addition to edge capacity, that is, a mapping ${\displaystyle c:V\to {\mathbb{R}}^{+},}$ such that the flow ${\displaystyle f}$ has to satisfy not only the capacity constraint and the conservation of flows, but also the vertex capacity constraint

${\displaystyle \sum _{i\in V}{f}_{iv}\le c(v)\mathrm{\forall }v\in V\mathrm{\setminus }\{s,t\}.}$

In other words, the amount of flow passing through a vertex cannot exceed its capacity. To find the maximum flow across ${\displaystyle N}$, we can transform the problem into the maximum flow problem in the original sense by expanding ${\displaystyle N}$. First, each ${\displaystyle v\in V}$ is replaced by ${\displaystyle v_{\text{in}}}$ and ${\displaystyle v_{\text{out}}}$, where ${\displaystyle v_{\text{in}}}$ is connected by edges going into ${\displaystyle v}$ and ${\displaystyle v_{\text{out}}}$ is connected to edges coming out from ${\displaystyle v}$, then assign capacity ${\displaystyle c(v)}$ to the edge connecting ${\displaystyle v_{\text{in}}}$ and ${\displaystyle v_{\text{out}}}$ (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 ${\displaystyle G=(V,E)}$ and two vertices ${\displaystyle s}$ and ${\displaystyle t}$, we are to find the maximum number of paths from ${\displaystyle s}$ to ${\displaystyle t}$. 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 ${\displaystyle N=(V,E)}$ from ${\displaystyle G}$, with ${\displaystyle s}$ and ${\displaystyle t}$ being the source and the sink of ${\displaystyle N}$ respectively, and assigning each edge a capacity of ${\displaystyle 1}$. In this network, the maximum flow is ${\displaystyle k}$ iff there are ${\displaystyle k}$ edge-disjoint paths.

2. The paths must be independent, i.e., vertex-disjoint (except for ${\displaystyle s}$ and ${\displaystyle t}$). We can construct a network ${\displaystyle N=(V,E)}$ from ${\displaystyle G}$ with vertex capacities, where the capacities of all vertices and all edges are ${\displaystyle 1}$. Then the value of the maximum flow is equal to the maximum number of independent paths from ${\displaystyle s}$ to ${\displaystyle t}$.

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 ${\displaystyle k}$, or at most ${\displaystyle k}$. Most variants of this problem are NP-complete, except for small values of ${\displaystyle k}$.

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 s,t ∈ V 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 {i, j} with i < 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 {i, j} 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 w_k + r_k – w_i is set to prevent team i from winning more than w_k + r_k. Let S be the set of all teams participating in the league and let

${\displaystyle r(S-\{k\})=\sum _{\genfrac{}{}{0ex}{}{i,j\in \{S-\{k\}\}}{i<j}}{r}_{ij}}$.

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 s,t ∈ V 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:

1. An edge with capacity [0, 1] between s and each s_i.
2. An edge with capacity [0, 1] between each d_i and t.
3. An edge with capacity [1, 1] between each pair of s_i and d_i.
4. An edge with capacity [0, 1] between each d_i and s_j, if source s_j is reachable with a reasonable amount of time and cost from the destination of flight i.
5. An edge with capacity [0, ∞] between s and t.

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 G' = (A ∪ B, E) 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, i∈A is connected to j∈B. A matching in G' 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 c 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.

1. Add a source node s and add edges from it to every factory node f_i with capacity p_i where p_i is the production rate of factory f_i.
2. Add a sink node t and add edges from all villages v_i to t with capacity d_i where d_i is the demand rate of village v_i.

Let G = (V, E) be this new network. There exists a circulation that satisfies the demand if and only if :

Maximum flow value(G) ${\displaystyle =\sum _{i\in v}{d}_i}$.

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: a_i ≥ 0 is the likelihood that pixel i belongs to the foreground, b_i ≥ 0 in the likelihood that pixel i belongs to the background, and p_ij 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

${\displaystyle q(A,B)=\sum _{i\in A}{a}_i+\sum _{i\in B}{b}_i-\sum _{\begin{array}{c}i,j\text{ adjacent}\\ |A\cap \{i,j\}|=1\end{array}}{p}_{ij}}$,

Indeed, for pixels in A (considered as the foreground), we gain a_i; for all pixels in B (considered as the background), we gain b_i. On the border, between two adjacent pixels i and j, we loose p_ij. It is equivalent to minimize the quantity

${\displaystyle q^{\prime }(A,B)=\sum _{i\in A}{b}_i+\sum _{i\in B}{a}_i+\sum _{\begin{array}{c}i,j\text{ adjacent}\\ |A\cap \{i,j\}|=1\end{array}}{p}_{ij}}$

because

${\displaystyle q(A,B)=\sum _{i\in A\cup B}{a}_i+\sum _{i\in A\cup B}{b}_i-q^{\prime }(A,B).}$

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 a_i. We connect the pixel i to the sink by an edge of weight b_i. We connect pixel i to pixel j with weight p_ij. 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 a_uv in addition to its capacity. If the flow through the edge is f_uv, then the total cost is a_uvf_uv. 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.