Maximum flow problem - AbsoluteAstronomy.com

Optimization (mathematics)

In mathematics, computational science, or management science, mathematical optimization refers to the selection of a best element from some set of available alternatives....

, the maximum flow problem is to find a feasible flow through a single-source, single-sink flow network

Flow network

In graph theory, a flow network is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Often in Operations Research, a directed graph is called a network, the vertices are called nodes and the edges are...

that is maximum.

The maximum flow problem can be seen as a special case of more complex network flow problems, such as the circulation problem

Circulation problem

The circulation problem and its variants is a generalisation of network flow problems, with the added constraint of a lower bound on edge flows, and with flow conservation also being required for the source and sink...

. The maximum value of an s-t flow is equal to the minimum capacity of an s-t cut

Cut (graph theory)

In graph theory, a cut is a partition of the vertices of a graph into two disjoint subsets. The cut-set of the cut is the set of edges whose end points are in different subsets of the partition. Edges are said to be crossing the cut if they are in its cut-set.In an unweighted undirected graph, the...

in the network, as stated in the max-flow min-cut theorem

Max-flow min-cut theorem

In optimization theory, the max-flow min-cut theorem states that in a flow network, the maximum amount of flow passing from the source to the sink is equal to the minimum capacity which when removed in a specific way from the network causes the situation that no flow can pass from the source to the...

History

The maximum flow problem was first formulated in 1954 by T. E. Harris as a simplified model of Soviet railway traffic flow.
In 1955, Lester R. Ford and Delbert R. Fulkerson

D. R. Fulkerson

Delbert Ray Fulkerson was a mathematician who co-developed the Ford-Fulkerson algorithm, one of the most well-known algorithms to solve the maximum flow problem in networks....

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 Goldeberg 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

be a network with

being the source and the sink of

respectively.

The capacity of an edge is a mapping

, denoted by

. It represents the maximum amount of flow that can pass through an edge.

A flow is a mapping

, denoted by

, subject to the following two constraints:

, for each

(capacity constraint: the flow of an edge cannot exceed its capacity)

, for each

(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

, where

is the source of

. It represents the amount of flow passing from the source to the sink.

The maximum flow problem is to maximize

, that is, to route as much flow as possible from

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

, and a flow

, we define the residual graph

with respect to

as follows.

1. The node set of

is the same as that of

.

2. Each edge

is with a capacity of

.

3. Each edge

is with a capacity of

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

Method	Complexity	Description
Linear programming Linear programming Linear programming is a mathematical method for determining a way to achieve the best outcome in a given mathematical model for some list of requirements represented as linear relationships...		Constraints given by the definition of a legal flow. See the linear program here.
Ford–Fulkerson algorithm	O(E max> f \|)	As long as there is an open path through the residual graph, send the minimum of the residual capacities on the path. The algorithm works only if all weights are integers. Otherwise it is possible that the Ford–Fulkerson algorithm will not converge to the maximum value.
Edmonds–Karp algorithm	O(VE²)	A specialization of Ford–Fulkerson, finding augmenting paths with breadth-first search Breadth-first search In graph theory, breadth-first search is a graph search algorithm that begins at the root node and explores all the neighboring nodes... .
Dinitz blocking flow algorithm	O(V²E)	In each phase the algorithms builds a layered graph with breadth-first search Breadth-first search In graph theory, breadth-first search is a graph search algorithm that begins at the root node and explores all the neighboring nodes... on the residual graph. The maximum flow in a layered graph can be calculated in O(VE) time, and the maximum number of the phases is n-1. In networks with unit capacities, Dinic's algorithm terminates in time.
General push-relabel maximum flow algorithm Relabel-to-front algorithm The push-relabel algorithm is one of the most efficient algorithms to compute a maximum flow. The general algorithm has O time complexity, while the implementation with FIFO vertex selection rule has O running time, the highest active vertex selection rule provides O complexity, and the...	O(V²E)	The push relabel algorithm maintains a preflow, i.e. a flow function with the possibility of excess in the vertices. The algorithm runs while there is a vertex with positive excess, i.e. an active vertex in the graph. The push operation increases the flow on a residual edge, and a height function on the vertices controls which residual edges can be pushed. The height function is changed with a relabel operation. The proper definitions of these operations guarantee that the resulting flow function is a maximum flow.
Push-relabel algorithm with FIFO vertex selection rule Relabel-to-front algorithm The push-relabel algorithm is one of the most efficient algorithms to compute a maximum flow. The general algorithm has O time complexity, while the implementation with FIFO vertex selection rule has O running time, the highest active vertex selection rule provides O complexity, and the...	O(V³)	Push-relabel algorithm variant which always selects the most recently active vertex, and performs push operations until the excess is positive or there are admissible residual edges from this vertex.
Dinitz blocking flow algorithm with dynamic trees	O(VE log(V))	The dynamic trees data structure speeds up the maximum flow computation in the layered graph to O(Elog(V)).
Push-relabel algorithm with dynamic trees Relabel-to-front algorithm The push-relabel algorithm is one of the most efficient algorithms to compute a maximum flow. The general algorithm has O time complexity, while the implementation with FIFO vertex selection rule has O running time, the highest active vertex selection rule provides O complexity, and the...	O(VE log(V²/E))	The algorithm builds limited size trees on the residual graph regarding to height function. These trees provide multilevel push operations.
Binary blocking flow algorithm		The value U corresponds to the maximum capacity of the network.
MPM (Malhotra, Pramodh-Kumar and Maheshwari) algorithm	O(V³)

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 with infinite capacity on each edge (See Fig. 4.1.1.).

Minimum path cover in directed acyclic graph

Given a directed acyclic graph

Directed acyclic graph

In mathematics and computer science, a directed acyclic graph , is a directed graph with no directed cycles. That is, it is formed by a collection of vertices and directed edges, each edge connecting one vertex to another, such that there is no way to start at some vertex v and follow a sequence of...

G = (V, E), we are to find the minimum number of paths

Path (graph theory)

In graph theory, a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence. A path may be infinite, but a finite path always has a first vertex, called its start vertex, and a last vertex, called its end vertex. Both of them...

to cover each vertex in V. We can construct a bipartite graph G' = (V_out∪V_in, E' ) from G, where

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

Then it can be shown that G' has a matching of size m if and only if there exists n-m 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

Bipartite graph

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...

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

E contains the edges in G directed from X to Y.

(s,x)∈E' for each x∈X and (y,t)∈E' for each y∈Y.

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∈Vf_iv ≤ c(v) for each 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 independent 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

s and t are the source and the sink of N respectively.
c(v) = 1 for each v∈V.
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.

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.