# Finding maximal flow in a transportation network

## Contents

## 1 Formulation of the problem

A *transportation network* is a directed graph [math]G = (V, E)[/math] in which a nonnegative capacity [math]c(e) \ge 0[/math] is assigned to each edge [math]e \in E[/math]. We assume that, along with each edge [math]e = (v, w) \in E[/math], the graph also contains the reverse edge [math]e^R = (w, v)[/math] (to which, if required, the zero capacity is assigned).

Let two vertices of a graph [math]G[/math] be marked, namely, the source [math]s[/math] and the sink [math]t[/math]. It can be assumed without loss of generality that all the other vertices lie on a path from [math]s[/math] to [math]t[/math]. A *flow* is a function [math]f: E \to \mathbb{R}[/math] that satisfies the following requirements:

- capacity constraint: [math]f(e) \le c(e)[/math];
- antisymmetry: [math]f(e^R) = -f(e)[/math];
- flow conservation law:

- [math] \forall v \ne s, t: \quad \sum_{e = (w, v)} f(e) = \sum_{e = (v, w)} f(e). [/math]

The *value of flow* is the total amount of flow from the source:

- [math] \left \vert f \right \vert = \sum_{e = (s, v)} f(e). [/math]

**Maximal flow problem in a transportation network.** It is required to find a flow with maximum value:

- [math]\left \vert f \right \vert \to \max.[/math]

## 2 Properties of the problem

The total flow out of the source is equal to the total flow into the sink:

- [math] \forall v \ne s, t: \quad \sum_{e = (s, v)} f(e) = \sum_{e = (v, t)} f(e). [/math]

(To prove this statement, it suffices to add up the flow conservation relations for all the vertices except for the source and sink.)

## 3 Variants of the problem

Depending on constraints on the capacity, the following cases may be distinguished:

- arbitrary positive capacity;
- integral capacity;
- unit capacity (in this case, the maximal flow is equal to the edge connectivity of the graph).

## 4 Algorithms for solving the problem

- The Ford-Fulkerson algorithm
^{[1]}and its versions^{[2]}^{[3]}with the complexity [math]O(n^2m)[/math] (for Dinic's algorithm). In the case of integral capacity bounded by [math]K[/math], the complexity is [math]O(Km)[/math]. - The preflow push algorithm
^{[4]}The complexity is [math]O(mn \ln n)[/math] (provided that Sleator-Tarjan dynamic trees are used^{[5]}^{[6]}).

Notation: [math]m[/math] is the number of edges, [math]n[/math] is the number of vertices.

## 5 References

- ↑ Ford, L R, Jr., and D R Fulkerson. “Maximal Flow Through a Network.” Canadian Journal of Mathematics 8 (1956): 399–404. doi:10.4153/CJM-1956-045-5.
- ↑ Edmonds, Jack, and Richard M Karp. “Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems.” Journal of the ACM 19, no. 2 (April 1972): 248–64. doi:10.1145/321694.321699.
- ↑ Диниц, Е. А. “Алгоритм решения задачи о максимальном потоке в сети со степенной оценкой.” Доклады АН СССР 194, no. 4 (1970): 754–57.
- ↑ Goldberg, Andrew V, and Robert Endre Tarjan. “A New Approach to the Maximum-Flow Problem.” Journal of the ACM 35, no. 4 (October 1988): 921–40. doi:10.1145/48014.61051.
- ↑ Sleator, Daniel D, and Robert Endre Tarjan. “A Data Structure for Dynamic Trees,” STOC'81, 114–22, New York, USA: ACM Press, 1981. doi:10.1145/800076.802464.
- ↑ Sleator, Daniel Dominic, and Robert Endre Tarjan. “Self-Adjusting Binary Search Trees.” Journal of the ACM 32, no. 3 (July 1985): 652–86. doi:10.1145/3828.3835.