Maximum flow problem

An example of a flow network with a maximum flow. The source is $s$, and the sink $t$. The numbers denote flow and capacity.

The maximum flow problem is to find a feasible flow through a single-source, single-sink flow network that is maximum.^[1] Sometimes it is defined as finding the value of such a flow. The maximum flow problem can be seen as special case of more complex network flow problems, as the circulation problem. The maximum s-t (source-to-sink) flow in a network is equal to the minimum s-t cut in the network, as stated in the Max-flow min-cut theorem.

Solutions

Given a directed graph $G(V,E)$, where each edge $u,v$ has a capacity $c(u,v)$, we want to find a maximal flow $f$ from the source $s$ to the sink $t$, subject to certain constraints. There are many ways of solving this problem:

Method	Complexity	Description
Linear programming		Constraints given by the definition of a legal flow. Optimize $\sum _{v\in V}f(s,v)$.
Ford-Fulkerson algorithm	$\scriptstyle O(E\cdot {\mathit {maxflow}})$	As long as there is an open path through the residual graph, send the minimum of the residual capacities on the path.
Edmonds-Karp algorithm	$O(VE^{2})$	A specialisation of Ford-Fulkerson, finding augmenting paths with breadth-first search.
Dinitz blocking flow algorithm	$O(V^{2}E)$	In each phase the algorithms builds layered graph with breadth-first search 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$.
General push-relabel maximum flow algorithm	$O(V^{2}E)$	The push relabel algorithm maintains a preflow, ie. a flow function with the possibility of excess in the vertices. The algorithms runs while there is vertex with positive excess, ie. 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 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	$O(V^{3})$	Push-relabel algorithm variant which always selects the most formerly actived vertex, and makes push operations until the excess is positive or there are admissible residual edges from this vertex.
Dinitz blocking flow algorithm with dynamic tree	$O(VE\log(V))$	The dynamic tree data structure speeds up the maximum flow computation in the layered graph to $O(E\log(V))$.
Push-relabel algorithm with using dynamic trees	$O(VE\log(V^{2}/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 [2]	$\scriptscriptstyle O(E\min(V^{2/3},{\sqrt {E}})\log(V^{2}/E)\log {U})$	The value U correspond to the maximum capacity of the network.

For a more extensive list, see ^[3].

References

1. ^ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein (2001). "26". Introduction to Algorithms (second edition ed.). MIT Press and McGraw-Hill. pp. 643–700. ISBN 0-262-53196-8. {{cite book}}: |edition= has extra text (help)CS1 maint: multiple names: authors list (link)
2. ^ Andrew V. Goldberg and S. Rao (1998). "Beyond the flow decomposition barrier". J. assoc. Comput. Mach. 45: 753–782. doi:10.1145/290179.290181.
3. ^ Andrew V. Goldberg and Robert E. Tarjan (1988). "A new approach to the maximum-flow problem". Journal of the ACM. 35 (4). ACM Press: 921–940. doi:10.1145/48014.61051. ISSN 0004-5411. {{cite journal}}: Unknown parameter |address= ignored (|location= suggested) (help)
4. ^ Joseph Cheriyan and Kurt Mehlhorn (1999). "An analysis of the highest-level selection rule in the preflow-push max-flow algorithm". Information Processing Letters. 69 (5): 239–242.
5. ^ Daniel D. Sleator and Robert E. Tarjan (1983). "A data structure for dynamic trees" (PDF). Journal of Computer and System Sciences. 26 (3): 362–391. doi:10.1016/0022-0000(83)90006-5. ISSN 0022-0000.
6. ^ Daniel D. Sleator and Robert E. Tarjan (1985). "Self-adjusting binary search trees" (PDF). Journal of the ACM. 32 (3). ACM Press: 652–686. doi:10.1145/3828.3835. ISSN 0004-5411. {{cite journal}}: Unknown parameter |address= ignored (|location= suggested) (help)

External links

• Lemon C++ library with several maximum flow implementations