Maximum flow problem

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.

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 electrical flow algorithm of Christiano, Kelner, Madry, and Spielman finds an approximately optimal maximum flow but only works in undirected graphs.

Definition

Let N = ( V , E ) be a network with s , t ∈ V being the source and the sink of N respectively.

The capacity of an edge is a mapping c : E → R + , denoted by c u v or c ( u , v ) . It represents the maximum amount of flow that can pass through an edge. A flow is a mapping f : E → R + , denoted by f u v or f ( u , v ) , subject to the following two constraints:

1. f u v ≤ c u v , for each ( u , v ) ∈ E (capacity constraint: the flow of an edge cannot exceed its capacity);
2. ∑ u : ( u , v ) ∈ E f u v = ∑ u : ( v , u ) ∈ E f v u , for each v ∈ V ∖ { s , t } (conservation of flows: the sum of the flows entering a node must equal the sum of the flows exiting a node, except for the source and the sink nodes).

The value of flow is defined by | f | = ∑ v : ( s , v ) ∈ E f s v , where s is the source of N . It represents the amount of flow passing from the source to the sink.

The maximum flow problem is to maximize | f | , that is, to route as much flow as possible from s to t .

Solutions

We can define the residual graph, which provides a systematic way to search for forward-backward operations in order to find the maximum flow.

Given a flow network G, and a flow f on G, we define the residual graph G f of G with respect to f as follows.

1. The node set of G f is the same as that of G.
2. Each edge e = ( u , v ) of G f is with a capacity of c e − f ( e ) .
3. Each edge e ′ = ( v , u ) of G f is with a capacity of f ( e ) .

The following table lists algorithms for solving the maximum flow problem.

For a more extensive list, see.

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.

Multi-source multi-sink maximum flow problem

Given a network N = (V,E) with a set of sources S = {s₁, ..., s_n} and a set of sinks T = {t₁, ..., t_m} instead of only one source and one sink, we are to find the maximum flow across 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 S and a consolidated sink connected by each vertex in T (also known as supersource and supersink) with infinite capacity on each edge (See Fig. 4.1.1.).

Minimum path cover in directed acyclic graph

Given a directed acyclic graph G = (V, E), we are to find the minimum number of vertex-disjoint paths to cover each vertex in V. We can construct a bipartite graph G' = (V_out∪V_in, E' ) from G, where

1. V_out = {v∈V: v has positive out-degree}.
2. V_in = {v∈V: v has positive in-degree}.
3. E' = {(u,v)∈V_out×V_in: (u,v)∈E}.

Then it can be shown, via König's theorem, that G' has a matching of size m if and only if there exists n-m vertex-disjoint paths that cover each vertex in G, where n is the number of vertices in G. Therefore, the problem can be solved by finding the maximum cardinality matching in G' instead.

Maximum cardinality bipartite matching

Given a bipartite graph G = (X∪Y, E), we are to find a maximum cardinality matching in 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 N = (X∪Y∪{s,t), E' }, where

1. E' contains the edges in G directed from X to Y.
2. (s,x)∈E' for each x∈X and (y,t)∈E' for each y∈Y.
3. c(e) = 1 for each e∈E' (See Fig. 4.3.1).

Then the value of the maximum flow in N is equal to the size of the maximum matching in G.

Maximum flow problem with vertex capacities

Given a network N = ( V , E ) , in which there is capacity at each node in addition to edge capacity, that is, a mapping c : V ↦ R + , denoted by c ( v ) , such that the flow f has to satisfy not only the capacity constraint and the conservation of flows, but also the vertex capacity constraint

∑ i ∈ V f i v ≤ c ( v ) ∀ v ∈ V ∖ { s , t } .

In other words, the amount of flow passing through a vertex cannot exceed its capacity. To find the maximum flow across N, we can transform the problem into the maximum flow problem in the original sense by expanding N. First, each v ∈ V is replaced by v in and v out , where v in is connected by edges going into v and v out is connected to edges coming out from v, then assign capacity c ( v ) to the edge connecting v in and v 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 edge-disjoint path

Given a directed graph G = (V, E) and two vertices s and t, we are to find the maximum number of edge-disjoint paths from s to t. This problem can be transformed to a maximum flow problem by constructing a network N = (V, E) from G with s and t being the source and the sink of N respectively and assign each edge with unit capacity.

Maximum independent (vertex-disjoint) path

Given a directed graph G = (V, E) and two vertices s and t, we are to find the maximum number of independent paths from s to t. Two paths are said to be independent if they do not have a vertex in common apart from s and t. We can construct a network N = (V, E) from G with vertex capacities, where

1. s and t are the source and the sink of N respectively.
2. c(v) = 1 for each v∈V.
3. c(e) = 1 for each e∈E.

Then the value of the maximum flow is equal to the maximum number of independent paths from s to t.

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 {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 r ( S − { k } ) = ∑ i , j ∈ { S − { k } } , i < j r i j . 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.

In order 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. In order 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) = ∑ i ∈ 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.