Editing Maximum flow problem (section)

==Algorithms==
The following table lists algorithms for solving the maximum flow problem.
Here, <math>V</math> and <math>E</math> denote the number of vertices and edges of the network.
The value <math>U</math> refers to the largest edge capacity after rescaling all capacities to integer values
(if the network contains [[Irrational number|irrational]] capacities, <math>U</math> may be infinite).

{| class="wikitable"
! Method
! Year
! Complexity
! Description
|-
| [[Linear programming]]
|
|
| Constraints given by the definition of a [[flow network|legal flow]]. See the [[Max-flow min-cut theorem#Linear program formulation|linear program]] here.
|-
| [[Ford–Fulkerson algorithm]]
| 1955
| <math>O(EU)</math>
| As long as there is an open path through the residual graph, send the minimum of the residual capacities on that path.
|-
| [[Edmonds–Karp algorithm]]
| 1970
| <math>O(VE^2)</math>
| A specialization of Ford–Fulkerson, finding augmenting paths with [[breadth-first search]].
|-
| [[Dinic's algorithm]]
| 1970
| <math>O(V^2E)</math>
| In each phase the algorithms builds a layered graph with [[breadth-first search]] on the [[residual graph]]. The maximum flow in a layered graph can be calculated in <math>O(VE)</math> time, and the maximum number of phases is <math>V-1</math>. In networks with unit capacities, Dinic's algorithm terminates in <math>O(\min\{V^{2/3}, E^{1/2}\}E)</math> time.
|-
| MKM (Malhotra, Kumar, Maheshwari) algorithm<ref>{{Cite journal | last1 = Malhotra | first1 =V.M.| last2 = Kumar | first2 = M. Pramodh| last3 = Maheshwari | first3 = S.N.| doi = 10.1016/0020-0190(78)90016-9| title = An <math>O(|V|^3)</math> algorithm for finding maximum flows in networks| journal = Information Processing Letters| volume = 7| issue = 6| pages = 277–278 | year = 1978| url =https://eprints.utas.edu.au/160/1/iplFlow.pdf}}</ref>
| 1978
| <math>O(V^3)</math>
| A modification of Dinic's algorithm with a different approach to constructing blocking flows. Refer to the [[#{{harvid|Malhotra|Kumar|Maheshwari|1978}}|original paper]].
|-
| [[Dinic's algorithm]] with dynamic trees
| 1983
| <math>O(VE \log V)</math>
| The [[dynamic trees]] data structure speeds up the maximum flow computation in the layered graph to <math>O(VE \log V)</math>.
|-
| General [[push–relabel algorithm]]<ref name="goldberg1988"/>
| 1986
| <math>O(V^2E)</math>
| 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 through which residual edges can flow be pushed. The height function is changed by the 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<ref name="goldberg1988"/>
| 1988
| <math>O(V^3)</math>
| Push-relabel algorithm variant which always selects the most recently active vertex, and performs push operations while the excess is positive and there are admissible residual edges from this vertex.
|-
|-
| [[Push–relabel algorithm]] with ''maximum distance'' vertex selection rule<ref name="cheriyan1988">{{cite book
 | last1 = Cheriyan
 | first1 = J.
 | last2 = Maheshwari
 | first2 = S. N.
 | title = Foundations of Software Technology and Theoretical Computer Science
 | chapter = Analysis of preflow push algorithms for maximum network flow
 | series = Lecture Notes in Computer Science
 | volume = 338
 | year = 1988
 | pages = 30–48
 | issn = 0302-9743
 | doi = 10.1007/3-540-50517-2_69
| isbn = 978-3-540-50517-4
 }}</ref>
| 1988
| <math>O(V^2 \sqrt{E})</math>
| Push-relabel algorithm variant which always selects the most distant vertex from <math>s</math> or <math>t</math> (i.e. the highest label vertex) but otherwise proceeds as the FIFO algorithm.
|-
| [[Push-relabel algorithm]] with dynamic trees<ref name="goldberg1988">{{Cite journal
 | last1 = Goldberg | first1 = A. V. | author-link1 = Andrew V. Goldberg
 | last2 = Tarjan | first2 = R. E. | author-link2 = Robert E. Tarjan
 | doi = 10.1145/48014.61051
 | title = A new approach to the maximum-flow problem
 | journal = [[Journal of the ACM]]
 | volume = 35
 | issue = 4
 | pages = 921
 | year = 1988
 | s2cid = 52152408
| doi-access = free
 }}</ref>
| 1988
| <math>O\left( VE \log \frac{V^2}{E} \right)</math>
| The algorithm builds limited size trees on the residual graph regarding to the height function. These trees provide multilevel push operations, i.e. pushing along an entire saturating ''path'' instead of a single edge.
|-
| KRT (King, Rao, Tarjan)'s algorithm<ref>{{Cite journal | last1 = King | first1 = V.| last2 = Rao | first2 = S.| last3 = Tarjan | first3 = R.| doi = 10.1006/jagm.1994.1044| title = A Faster Deterministic Maximum Flow Algorithm| journal = Journal of Algorithms| volume = 17| issue = 3| pages = 447–474| year = 1994| s2cid = 15493}}</ref>
| 1994
| <math>O\left( VE \log_{\frac{E}{V \log V}} V \right)</math>
|
|-
| Binary blocking flow algorithm<ref>{{Cite journal | last1 = Goldberg | first1 = A. V. | author-link1 = Andrew V. Goldberg| last2 = Rao | first2 = S. | doi = 10.1145/290179.290181 | title = Beyond the flow decomposition barrier | journal = [[Journal of the ACM]]| volume = 45 | issue = 5 | pages = 783 | year = 1998 | s2cid = 96030 | doi-access = free }}</ref>
| 1998
| <math>O\left( E \cdot \min\{V^{2/3}, E^{1/2}\} \cdot \log \frac{V^2}{E} \cdot \log U \right)</math>
|
|-
| James B Orlin's + KRT (King, Rao, Tarjan)'s algorithm<ref name="orlin">{{Cite book | last1 = Orlin | first1 = James B.| title = Proceedings of the forty-fifth annual ACM symposium on Theory of Computing| doi = 10.1145/2488608.2488705| chapter = Max flows in O(nm) time, or better| pages = 765–774| year = 2013| isbn = 9781450320290| citeseerx = 10.1.1.259.5759| s2cid = 207205207}}</ref>
| 2013
| <math>O(VE)</math>
| Orlin's algorithm solves max-flow in <math>O(VE)</math> time for <math>E \leq O(V^{\frac{16}{15} - \epsilon})</math> while KRT solves it in <math>O(VE)</math> for <math>E > V^{1+\epsilon}</math>.
|-
| Kathuria-Liu-Sidford algorithm<ref>{{cite book |last1=Kathuria |first1=T. |last2=Liu |first2=Y.P. |last3=Sidford |first3=A. |title=Unit Capacity Maxflow in Almost <math> O(m^{4/3}) </math> Time |date= 16–19 November 2020 |publisher=IEEE |location=Durham, NC, USA |pages=119–130}}</ref>
| 2020
| <math> E^{4/3+o(1)}U^{1/3} </math>
| Interior point methods and edge boosting using <math>\ell_p</math>-norm flows. Builds on earlier algorithm of Madry, which achieved runtime <math> \tilde O(E^{10/7}U^{1/7}) </math>.<ref>{{cite book |last1=Madry |first1=Aleksander |title=Computing Maximum Flow with Augmenting Electrical Flows |date=9-11 October 2016 |publisher=IEEE |location=New Brunswick, New Jersey |pages=593–602}}</ref>
|-
| BLNPSSSW / BLLSSSW algorithm<ref>{{cite book |last1=Brand |first1=J. vd |last2=Lee |first2=Y.T. |last3=Nanongkai |first3=D. |last4=Peng |first4=R. |last5=Saranurak |first5=T. |last6=Sidford |first6=A. |last7=Song |first7=Z. |last8=Wang |first8=D. |title=Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs |date= 16–19 November 2020 |publisher=IEEE |location=Durham, NC, USA |pages=919–930}}</ref>
<ref>{{cite arXiv |last1=Brand |first1=J. vd |last2=Lee |first2=Y.T. |last3=Liu |first3=Y.P. |last4=Saranurak |first4=T. |last5=Sidford |first5=A |last6=Song |first6=Z. |last7=Wang |first7=D. |title=Minimum Cost Flows, MDPs, and ℓ1-Regression in Nearly Linear Time for Dense Instances |year=2021 |class=cs.DS |eprint=2101.05719}}</ref>
| 2020
| <math>\tilde O((E + V^{3/2}) \log U)</math>
| Interior point methods and dynamic maintenance of electric flows with expander decompositions.
|-
| Gao-Liu-Peng algorithm<ref>{{Cite arXiv | last1 = Gao | first1 = Y.| last2 = Liu | first2 = Y.P.| last3 = Peng | first3 = R.| title = Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg-Rao| year = 2021| class = cs.DS| eprint = 2101.07233}}</ref>
| 2021
| <math>\tilde O(E^{\frac 32 - \frac 1{328}} \log U)</math>
| Gao, Liu, and Peng's algorithm revolves around dynamically maintaining the augmenting electrical flows at the core of the interior point method based algorithm from [Mądry JACM ‘16]. This entails designing data structures that, in limited settings, return edges with large electric energy in a graph undergoing resistance updates.
|-
| Chen, Kyng, Liu, Peng, Gutenberg and Sachdeva's algorithm<ref name="almost linear">{{Cite arXiv | last1 = Chen | first1 = L.| last2 = Kyng | first2 = R.| last3 = Liu | first3 = Y.P.| last4 = Gutenberg | first4 = M.P. | last5 = Sachdeva | first5 = S. | title = Maximum Flow and Minimum-Cost Flow in Almost-Linear Time| year = 2022| class = cs.DS| eprint = 2203.00671}}</ref>
| 2022
|<math>O(E^{1+o(1)} \log U)</math>
The exact complexity is not stated clearly in the paper, but appears to be <math>E \exp O(\log^{7/8} E \log \log E) \log U</math>
| Chen, Kyng, Liu, Peng, Gutenberg and Sachdeva's algorithm solves maximum flow and minimum-cost flow in almost linear time by building the flow through a sequence of <math>E^{1+o(1)}</math> approximate undirected minimum-ratio cycles, each of which is computed and processed in amortized <math>E^{o(1)}</math> time using a dynamic data structure.
|-
| Bernstein, Blikstad, Saranurak, Tu<ref>{{Cite arXiv | last1 = Bernstein | first1 = A. | last2 = Blikstad | first2 = J. | last3 = Saranurak | first3 = T. | last4 = Tu | first4 = T. | title = Maximum Flow by Augmenting Paths in <math>n^{2 + o(1)}</math> Time | year = 2024 | class = cs.DS | eprint = 2406.03648}}</ref>
| 2024
|<math>O(n^{2 + o(1)} \log U)</math> randomized algorithm when the edge capacities come from the set <math>\{1, \dots, U\}</math>
| The algorithm is a variant of the push-relabel algorithm by introducing the ''weighted'' variant. The paper establishes a weight function on directed and acyclic graphs (DAG), and attempts to imitate it on general graphs using directed expander hierarchies, which induce a natural vertex ordering that produces the weight function similar to that of the DAG special case. The randomization aspect (and subsequently, the <math>n^{o(1)}</math> factor) comes from the difficulty in applying directed expander hierarchies to the computation of ''sparse cuts'', which do not allow for natural dynamic updating.
|}

For additional algorithms, see {{harvtxt|Goldberg|Tarjan|1988}}.