{{Short description|Computational problem in graph theory}} {{Use dmy dates|date=May 2022}} {{CS1 config|mode=cs1}} alt=Flow network for the problem: Each human (r''i'') is willing to adopt a cat (w''i''1) and/or a dog (w''i''2). However each pet (p''i'') has a preference for only a subset of the humans. Find any matching of pets to humans such that the maximum number of pets are adopted by one of its preferred humans.|thumb|252x252px|Flow network for the problem: Each human (r''i'') is willing to adopt a cat (w''i''1) and/or a dog (w''i''2). However each pet (p''i'') has a preference for only a subset of the humans. Find any matching of pets to humans such that the maximum number of pets are adopted by one of its preferred humans. In optimization theory, '''maximum flow problems''' involve finding a feasible flow through a flow network that obtains the maximum possible flow rate.

The maximum flow problem can be seen as a special case of more complex network flow problems, such as the circulation problem. The maximum value of an s-t flow (i.e., flow from source s to sink t) is equal to the minimum capacity of an s-t cut (i.e., cut severing s from t) in the network, as stated in the max-flow min-cut theorem.

==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.<ref name=":0">{{Cite journal | last1 = Schrijver | first1 = A. | title = On the history of the transportation and maximum flow problems | doi = 10.1007/s101070100259 | journal = Mathematical Programming | volume = 91 | issue = 3 | pages = 437–445 | year = 2002 | citeseerx = 10.1.1.23.5134 | s2cid = 10210675 }}</ref><ref>{{Cite book | doi = 10.1007/0-387-25837-X_5 | first1 = Saul I. | last1 = Gass| first2 = Arjang A. | last2 = Assad | chapter = Mathematical, algorithmic and professional developments of operations research from 1951 to 1956 | title = An Annotated Timeline of Operations Research | series = International Series in Operations Research & Management Science | volume = 75 | pages = 79–110 | year = 2005 | doi-broken-date = 1 July 2025 | isbn = 978-1-4020-8116-3 }}</ref><ref name=":2">{{cite journal | first1 = T. E. | last1 = Harris | author-link1 = Ted Harris (mathematician) | first2 = F. S. | last2 = Ross | year = 1955 | title = Fundamentals of a Method for Evaluating Rail Net Capacities | journal = Research Memorandum| url = http://www.dtic.mil/dtic/tr/fulltext/u2/093458.pdf| archive-url = https://web.archive.org/web/20140108021700/http://www.dtic.mil/dtic/tr/fulltext/u2/093458.pdf| url-status = dead| archive-date = 8 January 2014}}</ref> In 1955, Lester R. Ford, Jr. and Delbert R. Fulkerson created the first known algorithm, the Ford–Fulkerson algorithm.<ref name=":1">{{Cite journal | last1 = Ford | first1 = L. R. | author-link1 = L. R. Ford, Jr.| last2 = Fulkerson | first2 = D. R. | author-link2 = D. R. Fulkerson| doi = 10.4153/CJM-1956-045-5 | title = Maximal flow through a network | journal = Canadian Journal of Mathematics| volume = 8 | pages = 399–404 | year = 1956 | doi-access = free }}</ref><ref name=":3">Ford, L.R., Jr.; Fulkerson, D.R., ''Flows in Networks'', Princeton University Press (1962).</ref> In their 1955 paper,<ref name=":1" /> Ford and Fulkerson wrote that the problem of Harris and Ross is formulated as follows (see<ref name=":0" /> p.&nbsp;5):<blockquote>Consider a rail network connecting two cities by way of a number of intermediate cities, where each link of the network has a number assigned to it representing its capacity. Assuming a steady state condition, find a maximal flow from one given city to the other.</blockquote>In their book ''Flows in Networks'',<ref name=":3" /> in 1962, Ford and Fulkerson wrote:<blockquote>It was posed to the authors in the spring of 1955 by T. E. Harris, who, in conjunction with General F. S. Ross (Ret.), had formulated a simplified model of railway traffic flow, and pinpointed this particular problem as the central one suggested by the model [11].</blockquote>where [11] refers to the 1955 secret report ''Fundamentals of a Method for Evaluating Rail net Capacities'' by Harris and Ross<ref name=":2" /> (see<ref name=":0" /> p.&nbsp;5).

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 algorithms of Sherman<ref>{{Cite book | last = Sherman | first = Jonah | chapter = Nearly Maximum Flows in Nearly Linear Time | doi = 10.1109/FOCS.2013.36 | title = Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science | pages = 263–269 | year = 2013 | arxiv = 1304.2077 | isbn = 978-0-7695-5135-7 | s2cid = 14681906 }}</ref> and Kelner, Lee, Orecchia and Sidford,<ref>{{Cite book | last1 = Kelner | first1 = J. A. | last2 = Lee | first2 = Y. T. | last3 = Orecchia | first3 = L. | last4 = Sidford | first4 = A. | chapter = An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations | doi = 10.1137/1.9781611973402.16 | title = Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | pages = 217 | year = 2014 | isbn = 978-1-61197-338-9 | chapter-url = http://math.mit.edu/~kelner/Publications/Docs/klos_maxflow_main.pdf | arxiv = 1304.2338 | s2cid = 10733914 | url-status = dead | archive-url = https://web.archive.org/web/20160303170302/http://math.mit.edu/~kelner/Publications/Docs/klos_maxflow_main.pdf | archive-date =2016-03-03 }}</ref><ref>{{cite web | url = http://web.mit.edu/newsoffice/2013/new-algorithm-can-dramatically-streamline-solutions-to-the-max-flow-problem-0107.html | title = New algorithm can dramatically streamline solutions to the 'max flow' problem | first = Helen | last = Knight | date = 7 January 2014 | access-date = 8 January 2014 | publisher = MIT News | archive-date = 26 February 2014 | archive-url = https://web.archive.org/web/20140226211541/http://web.mit.edu/newsoffice/2013/new-algorithm-can-dramatically-streamline-solutions-to-the-max-flow-problem-0107.html | url-status = dead }}</ref> respectively, find an approximately optimal maximum flow but only work in undirected graphs.

In 2013 James B. Orlin published a paper describing an <math>O(|V| |E|)</math> algorithm.<ref name="orlin" />

In 2022 Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva published an almost-linear time algorithm running in <math>O(|E|^{1+o(1)})</math> for the minimum-cost flow problem of which the maximum flow problem is a particular case.<ref name="almost linear" /><ref>{{Cite web |last=Klarreich |first=Erica |date=2022-06-08 |title=Researchers Achieve 'Absurdly Fast' Algorithm for Network Flow |url=https://www.quantamagazine.org/researchers-achieve-absurdly-fast-algorithm-for-network-flow-20220608/ |access-date=2022-06-08 |website=Quanta Magazine |language=en}}</ref> For the single-source shortest path (SSSP) problem with negative weights – another particular case of a minimum-cost flow problem – an algorithm running in almost-linear time has also been reported.<ref>{{Cite arXiv |last1=Bernstein |first1=Aaron |last2=Nanongkai |first2=Danupon |last3=Wulff-Nilsen |first3=Christian |date=2022-10-30 |title=Negative-Weight Single-Source Shortest Paths in Near-linear Time |class=cs.DS |eprint=2203.03456 }}</ref><ref>{{Cite web |last=Brubaker |first=Ben |date=2023-01-18 |title=Finally, a Fast Algorithm for Shortest Paths on Negative Graphs |url=https://www.quantamagazine.org/finally-a-fast-algorithm-for-shortest-paths-on-negative-graphs-20230118/ |access-date=2023-01-25 |website=Quanta Magazine |language=en}}</ref> Both algorithms were deemed best papers at the 2022 Symposium on Foundations of Computer Science.<ref>{{Cite web |title=FOCS 2022 |url=https://focs2022.eecs.berkeley.edu/awards.html |access-date=2023-01-25 |website=focs2022.eecs.berkeley.edu}}</ref><ref>{{Cite web |last=Santosh |first=Nagarakatte |title=FOCS 2022 Best Paper Award for Prof. Aaron Bernstein's Paper |url=https://www.cs.rutgers.edu/news-events/news/news-item/focs-2022-best-paper-award-for-prof-aaron-bernstein-s-paper |access-date=2023-01-25 |website=www.cs.rutgers.edu |language=en-gb}}</ref>

==Definition== thumb|upright=0.8|A flow network, with source ''s'' and sink ''t''. The numbers next to the edges are the capacities.

First we establish some notation: * Let <math>N = (V, E)</math> be a flow network with <math>s, t \in V</math> being the source and the sink of <math>N</math> respectively. * If <math>g</math> is a function on the edges of <math>N</math> then its value on <math>(u,v) \in E</math> is denoted by <math>g_{uv}</math> or <math>g(u,v).</math>

'''Definition.''' The '''capacity''' of an edge is the maximum amount of flow that can pass through an edge. Formally it is a map <math>c: E \to \R^+.</math>

'''Definition.''' A '''flow''' is a map <math>f : E \to \R</math> that satisfies the following: *''Capacity constraint''. The flow of an edge cannot exceed its capacity, in other words: <math>f_{uv} \leq c_{uv}</math> for all <math>(u, v) \in E.</math> * ''Conservation of flows.'' The sum of the flows entering a node must equal the sum of the flows exiting that node, except for the source and the sink. Or: ::<math>\forall v \in V \setminus \{s, t\}: \quad \sum_{u:(u, v) \in E, f_{uv}>0} f_{uv} = \sum_{u:(v, u) \in E, f_{vu}>0} f_{vu}.</math>

''Remark''. Flows are skew symmetric: <math>f_{uv} = -f_{vu}</math> for all <math>(u, v) \in E.</math>

'''Definition.''' The '''value of flow''' is the amount of flow passing from the source to the sink. Formally for a flow <math>f : E \to \R^+</math> it is given by: :<math>|f| = \sum_{v:\ (s,v) \in E} f_{sv} = \sum_{u:\ (u,t) \in E} f_{ut}.</math>

'''Definition.''' The '''maximum flow problem''' is to route as much flow as possible from the source to the sink, in other words find the flow <math>f_\textrm{max}</math> with maximum value.

Note that several maximum flows may exist, and if arbitrary real (or even arbitrary rational) values of flow are permitted (instead of just integers), there is either exactly one maximum flow, or infinitely many, since there are infinitely many linear combinations of the base maximum flows. In other words, if we send <math>x</math> units of flow on edge <math>u</math> in one maximum flow, and <math>y > x</math> units of flow on <math>u</math> in another maximum flow, then for each <math>\Delta \in [0, y-x]</math> we can send <math>x+\Delta</math> units on <math>u</math> and route the flow on remaining edges accordingly, to obtain another maximum flow. If flow values can be any real or rational numbers, then there are infinitely many such <math>\Delta</math> values for each pair <math>x, y</math>.

==Algorithms== The following tables show the historical development of algorithms for solving the maximum flow problem. Many of the listed publications include similar tables comparing their results to earlier works.

===Strongly polynomial=== A strongly-polynomial time algorithm has polynomial time bounds that depend only on the number of inputs, but do not depend on the magnitude of these numbers. Here, the inputs are the vertices (numbered below as <math>V</math>) and edges (numbered as <math>E</math>). The complexity of each algorithm is stated using big O notation.

{| class="wikitable" ! Method ! Year ! Complexity ! Description |- | Edmonds–Karp algorithm<ref>{{cite journal | last1 = Edmonds | first1 = Jack | last2 = Karp | first2 = Richard M. | date = April 1972 | doi = 10.1145/321694.321699 | issue = 2 | journal = Journal of the ACM | pages = 248–264 | title = Theoretical improvements in algorithmic efficiency for network flow problems | volume = 19}} Previously announced at the International Conference on Combinatorial Structures and their Applications, Calgary, Alberta, 1969, {{MR|0266680}}.</ref> | 1969 | <math>O(VE^2)</math> | A specialization of Ford–Fulkerson, finding augmenting paths with breadth-first search. |- | Dinic's algorithm<ref>{{cite journal | last = Dinic | first = E. A. | author-link = Yefim Dinitz | journal = Doklady Akademii Nauk SSSR | mr = 287976 | pages = 754–757 | title = An algorithm for the solution of the problem of maximal flow in a network with power estimation | volume = 194 | year = 1970}}</ref> | 1970 | <math>O(V^2E)</math> (arbitrary weights)<br><math>O(\min\{V^{2/3}, E^{1/2}\}E)</math> (unit weights) | Repeated phases that build a "layered" subgraph of residual graph edges belonging to shortest paths, using breadth-first search, and then find a blocking flow (a maximum flow in this layered graph) in time <math>O(VE)</math> per phase. The shortest path length increases in each phase so there are at most <math>V-1</math> phases. |- | Karzanov's algorithm<ref>{{cite journal | last = Karzanov | first = A. V. | journal = Doklady Akademii Nauk SSSR | mr = 343879 | pages = 49–52 | title = The problem of finding the maximal flow in a network by the method of preflows | volume = 215 | year = 1974}}</ref> | 1974 | <math>O(V^3)</math> | A predecessor to the push-relabel algorithm using preflows (flow functions allowing excess at vertices) to find a blocking flow in each phase of Dinic's algorithm in time <math>O(V^2)</math> per phase. The first cubic-time flow algorithm. |- | Cherkassky's algorithm<ref>{{cite journal | last = Čerkasskiĭ | first = B. V. | journal = Mathematical Methods for the Solution of Economic Problems | mr = 503654 | pages = 117–126 | title = An algorithm for the construction of the maximal flow in a network with a labor expenditure of <math>O(n^2\sqrt{p})</math> actions | volume = 7 | year = 1977}}</ref> | 1977 | <math>O\bigl(V^2 \sqrt{E}\bigr)</math> | Combines the blocking flow methods of Dinic (within blocks of consecutive BFS layers) and Karzanov (to combine blocks). The first subcubic strongly polynomial time bound for sparse graphs. Remained best for some values of <math>E</math> until KRT 1988. |- | Malhotra, Kumar, and Maheshwari<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> | Not an improvement in complexity over Karzanov, but a simplification. Finds blocking flows by repeatedly finding a "reference node" of the layered graph and a flow that saturates all its incoming or outgoing edges, in time proportional to the number of nodes plus the number of saturated edges. |- | Galil's algorithm<ref>{{cite journal | last = Galil | first = Zvi | author-link = Zvi Galil| doi = 10.1007/BF00264254 | issue = 3 | journal = Acta Informatica | mr = 587133 | pages = 221–242 | title = An <math>O(V^{5/3}E^{2/3})</math> algorithm for the maximal flow problem | volume = 14 | year = 1980}} Preliminary version, "A new algorithm for the maximal flow problem", ''19th Annual Symposium on Foundations of Computer Science (FOCS)'', 1978.</ref> | 1978 | <math>O(V^{5/3}E^{2/3})</math> | Modifies Cherkasky's algorithm by replacing the method for finding flows within blocks of consecutive layers. |- | Galil, Naamad, and {{nowrap|Shiloach<ref>{{cite journal | last1 = Galil | first1 = Zvi | author1-link = Zvi Galil | last2 = Naamad | first2 = Amnon | doi = 10.1016/0022-0000(80)90035-5 | issue = 2 | journal = Journal of Computer and System Sciences | pages = 203–217 | title = An <math>O\bigl(EV(\log V)^2\bigr)</math> algorithm for the maximal flow problem | volume = 21 | year = 1980}} Circulated as an unpublished manuscript in 1978, and published in preliminary form as "Network flow and generalized path compression", ''20th Annual Symposium on Foundations of Computer Science (FOCS)'', 1979, {{doi|10.1145/800135.804394}}.</ref><ref>{{cite report|first=Yossi|last=Shiloach|title=An <math>O(nI\log^2 I)</math> maximum-flow algorithm|type=Technical Report STAN-CS-78-802|publisher=Stanford University Computer Science Department}} As cited by {{harvtxt|Galil|Naamad|1980}}</ref>}} | 1978 | <math>O\bigl(VE(\log V)^2\bigr)</math> | Uses tree contraction on a breadth-first search forest of the layered graph to speed up blocking flows. The first of many <math>O(VE\operatorname{polylog}V)</math> algorithms, still the best polynomial exponents for a strongly polynomial algorithm.

|- | Blocking flow with link/cut trees.<ref>{{cite journal | last1 = Sleator | first1 = Daniel D. | author1-link = Daniel Sleator | last2 = Tarjan | first2 = Robert Endre | author2-link = Robert Tarjan | doi = 10.1016/0022-0000(83)90006-5 | issue = 3 | journal = Journal of Computer and System Sciences | mr = 710253 | pages = 362–391 | title = A data structure for dynamic trees | volume = 26 | year = 1983}} Preliminary version, ''13th ACM Symposium on Theory of Computing (STOC)'', 1981, {{doi|10.1145/800076.802464}}</ref> | 1981 | <math>O(VE \log V)</math> | Introduces the link/cut tree data structure and uses it to find augmenting paths in layered networks in logarithmic amortized time per path. |- | Push–relabel algorithm with link/cut 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}} Preliminary version, ''18th Annual ACM Symposium on Theory of Computing (STOC)'', 1986, {{doi|10.1145/12130.12144}}</ref> | 1986 | <math>O\left( VE \log \frac{V^2}{E} \right)</math> | The push-relabel algorithm maintains a preflow, and a height function estimating residual distance to the sink. It modifies the preflow by pushing excess to lower-height vertices and increases the height function at vertices without residual edges to lower heights, until all excess returns to the source. Link/cut trees allow pushes along paths rather than one edge at a time. |- | Cheriyan and Hagerup<ref>{{cite journal | last1 = Cheriyan | first1 = Joseph | last2 = Hagerup | first2 = Torben | doi = 10.1137/S0097539791221529 | issue = 2 | journal = SIAM Journal on Computing | mr = 1320205 | pages = 203–226 | title = A randomized maximum-flow algorithm | volume = 24 | year = 1995}} Preliminary version in ''30th Annual Symposium on Foundations of Computer Science (FOCS)'', 1989, {{doi | 10.1109/SFCS.1989.63465}}</ref> | 1989 | randomized, <math>O\bigl(VE + V^2(\log V)^2\bigr)</math> with high probability | Push-relabel on a subgraph to which one edge is added at a time, prioritizing pushes of high excess amounts, with randomly permuted adjacency lists |- | Alon<ref>{{cite journal | last = Alon | first = Noga | author-link = Noga Alon | doi = 10.1016/0020-0190(90)90024-R | issue = 4 | journal = Information Processing Letters | mr = 1066123 | pages = 201–204 | title = Generating pseudo-random permutations and maximum flow algorithms | url = https://www.cs.tau.ac.il/~nogaa/PDFS/perm1.pdf | volume = 35 | year = 1990}} Cited as a 1989 manuscript by Cheriyan, Hagerup, and Mehlhorn 1990.</ref> | 1989 |<math>O(VE+V^{8/3}\log V)</math> | Derandomization of Cheriyan and Hagerup |- | Cheriyan, Hagerup, and Mehlhorn<ref>{{cite journal | last1 = Cheriyan | first1 = Joseph | last2 = Hagerup | first2 = Torben | last3 = Mehlhorn | first3 = Kurt | author3-link = Kurt Mehlhorn | doi = 10.1137/S0097539791278376 | issue = 6 | journal = SIAM Journal on Computing | mr = 1417893 | pages = 1144–1170 | title = An <math>o(n^3)</math>-time maximum-flow algorithm | volume = 25 | year = 1996| hdl = 11858/00-001M-0000-0014-B08A-3 | hdl-access = free }} Preliminary version, "Can a maximum flow be computed in <math>o(nm)</math> time?", ''17th International Colloquium on Automata, Languages and Programming'' (ICALP), 1990, {{doi | 10.1007/BFb0032035}}</ref> | 1990 | <math>\displaystyle O\left(\frac{V^3}{\log V}\right)</math> | Uses Alon's derandomization of Cheriyan and Hagerup with ideas related to the Method of Four Russians to speed up the search for height-reducing edges on which to push excess. |- | King, Rao, and Tarjan<ref>{{cite conference | last1 = King | first1 = Valerie | author1-link = Valerie King | last2 = Rao | first2 = S. | last3 = Tarjan | first3 = Robert Endre | author3-link = Robert Tarjan | editor-last = Frederickson | editor-first = Greg N. | contribution = A faster deterministic maximum flow algorithm | contribution-url = https://dl.acm.org/citation.cfm?id=139404.139438 | pages = 157–164 | title = Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 27-29 January 1992, Orlando, Florida, USA | year = 1992}}</ref> | 1992 | <math>O(VE+V^{2+\varepsilon})</math><br/> for any <math>\varepsilon>0</math> | Another derandomization of Cheriyan and Hagerup. Preliminary version of King, Rao, and Tarjan 1994 with weaker bounds. |- | Phillips and Westbrook<ref>{{cite journal | last1 = Phillips | first1 = Steven J. | last2 = Westbrook | first2 = Jeffery R. | author-link = Jeff Westbrook | doi = 10.1007/PL00009214 | issue = 3 | journal = Algorithmica | pages = 245–261 | title = On-line load balancing and network flow | volume = 21 | year = 1998}} Preliminary version, ''25th ACM Symposium on Theory of Computing (STOC)'', 1993, {{doi|10.1145/167088.167201}}.</ref> | 1993 | <math>O(VE\log_{E/V}V+V(\log V)^{2+\varepsilon})</math><br/> for any <math>\varepsilon>0</math> | Improved from King, Rao, and Tarjan 1992 using similar ideas. |- | King, Rao, and Tarjan<ref>{{cite journal | last1 = King | first1 = V. | author1-link = Valerie King | last2 = Rao | first2 = S. | author2-link = Satish B. Rao | last3 = Tarjan | first3 = R. | author3-link = Robert Tarjan | doi = 10.1006/jagm.1994.1044 | issue = 3 | journal = Journal of Algorithms | mr = 1300259 | pages = 447–474 | title = A faster deterministic maximum flow algorithm | volume = 17 | year = 1994}}</ref> | 1994 | <math>O\left( VE \log_{\frac{E}{V \log V}} V \right)</math> | Improved from Phillips and Westbrook using similar ideas. |- | Orlin<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> | Applies a pseudopolynomial algorithm of Goldberg and Rao to a compressed network, maintained using data structures for dynamic transitive closure. Takes time <math>O\bigr(VE+E^{31/16}(\log V)^2\bigr)</math>, which simplifies to <math>O(VE)</math> for <math>E = O(V^{16/15 - \varepsilon})</math>, while previous bounds simplify to <math>O(VE)</math> for <math>E =\Omega(V^{1+\epsilon})</math>. |- | Orlin and Gong<ref>{{cite journal | last1 = Orlin | first1 = James B. | last2 = Gong | first2 = Xiao-yue | doi = 10.1002/net.22001 | hdl = 1721.1/134021 | issue = 2 | journal = Networks | mr = 4264487 | pages = 287–321 | title = A fast maximum flow algorithm | volume = 77 | year = 2021| hdl-access = free }}</ref> | 2021 | <math>\displaystyle O\left(\frac{VE\log V}{\log\log V+\log\tfrac{E}{V}}\right)</math> | Based on a pseudopolynomial algorithm of Ahuja, Orlin, and Tarjan. Faster than King, Rao, and Tarjan and does not use link/cut trees, but not faster than Orlin + KRT. |}

===Pseudo-polynomial and weakly polynomial=== In parallel to the development of strongly-polynomial flow algorithms, there has been a long line of pseudo-polynomial and weakly polynomial time bounds, whose running time depends on the magnitude of the input capacities. Here, the value <math>U</math> refers to the largest edge capacity after rescaling all capacities to integer values. (If the network contains irrational capacities, this rescaling may not be possible and these algorithms may not produce exact solutions or may fail to converge even to an approximate solution.) The difference between pseudo-polynomial and weakly polynomial is that a pseudo-polynomial bound may be polynomial in <math>U</math>, but for a weakly polynomial bound it can be polynomial only in <math>\log U</math>.

{| class="wikitable" ! Method ! Year ! Complexity ! Description |- | Ford–Fulkerson algorithm<ref>{{cite journal | last1 = Ford | first1 = L. R. Jr. | author1-link = L. R. Ford Jr. | last2 = Fulkerson | first2 = D. R. | author2-link = D. R. Fulkerson | doi = 10.4153/CJM-1956-045-5 | journal = Canadian Journal of Mathematics | mr = 79251 | pages = 399–404 | title = Maximal flow through a network | volume = 8 | year = 1956}}</ref> | 1956 | <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. |- | 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> | |- | 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. |}

==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.'''

The claim is not only that the value of the flow is an integer, which follows directly from the max-flow min-cut theorem, but that the flow on ''every edge'' is integral. This is crucial for many combinatorial applications (see below), where the flow across an edge may encode whether the item corresponding to that edge is to be included in the set sought or not.

==Application==

===Multi-source multi-sink maximum flow problem=== thumb|right|Fig. 4.1.1. Transformation of a multi-source multi-sink maximum flow problem into a single-source single-sink maximum flow problem Given a network <math>N = (V, E)</math> with a set of sources <math>S = \{s_1, \ldots, s_n\}</math> and a set of sinks <math>T = \{t_1, \ldots, t_m\}</math> instead of only one source and one sink, we are to find the maximum flow across <math>N</math>. We can transform the multi-source multi-sink problem into a maximum flow problem by adding a ''consolidated source'' connecting to each vertex in <math>S</math> and a ''consolidated sink ''connected by each vertex in <math>T</math> (also known as ''supersource'' and ''supersink'') with infinite capacity on each edge (See Fig. 4.1.1.).

===Maximum cardinality bipartite matching=== thumb|right|Fig. 4.3.1. Transformation of a maximum bipartite matching problem into a maximum flow problem Given a bipartite graph <math>G = (X \cup Y, E)</math>, we are to find a maximum cardinality matching in <math>G</math>, 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 <math>N = (X \cup Y \cup \{s,t\}, E')</math>, where # <math>E'</math> contains the edges in <math>G</math> directed from <math>X</math> to <math>Y</math>. # <math>(s,x) \in E'</math> for each <math>x \in X</math> and <math>(y,t) \in E'</math> for each <math>y \in Y</math>. # <math>c(e) = 1</math> for each <math>e \in E'</math> (See Fig. 4.3.1).

Then the value of the maximum flow in <math>N</math> is equal to the size of the maximum matching in <math>G</math>, and a maximum cardinality matching can be found by taking those edges that have flow <math>1</math> in an integral max-flow.

===Minimum path cover in directed acyclic graph=== Given a directed acyclic graph <math>G = (V, E)</math>, we are to find the minimum number of vertex-disjoint paths to cover each vertex in <math>V</math>. We can construct a bipartite graph <math>G' = (V_\textrm{out} \cup V_\textrm{in}, E')</math> from <math>G</math>, where # <math>V_\textrm{out} = \{ v_\textrm{out} \mid v \in V \land v \text{ has outgoing edge(s)} \}</math> # <math>V_\textrm{in} = \{ v_\textrm{in} \mid v \in V \land v \text{ has incoming edge(s)} \}</math> # <math>E' = \{(u_\textrm{out}, v_\textrm{in}) \in V_{out} \times V_{in} \mid (u, v) \in E \}</math>.

Then it can be shown that <math>G'</math> has a matching <math>M</math> of size <math>m</math> if and only if <math>G</math> has a vertex-disjoint path cover <math>C</math> containing <math>m</math> edges and <math>n-m</math> paths, where <math>n</math> is the number of vertices in <math>G</math>. Therefore, the problem can be solved by finding the maximum cardinality matching in <math>G'</math> instead.

Assume we have found a matching <math>M</math> of <math>G'</math>, and constructed the cover <math>C</math> from it. Intuitively, if two vertices <math>u_\mathrm{out}, v_\mathrm{in}</math> are matched in <math>M</math>, then the edge <math>(u, v)</math> is contained in <math>C</math>. Clearly the number of edges in <math>C</math> is <math>m</math>. To see that <math>C</math> is vertex-disjoint, consider the following: # Each vertex <math>v_\textrm{out}</math> in <math>G'</math> can either be ''non-matched'' in <math>M</math>, in which case there are no edges leaving <math>v</math> in <math>C</math>; or it can be ''matched'', in which case there is exactly one edge leaving <math>v</math> in <math>C</math>. In either case, no more than one edge leaves any vertex <math>v</math> in <math>C</math>. # Similarly for each vertex <math>v_\textrm{in}</math> in <math>G'</math> – if it is matched, there is a single incoming edge into <math>v</math> in <math>C</math>; otherwise <math>v</math> has no incoming edges in <math>C</math>. Thus no vertex has two incoming or two outgoing edges in <math>C</math>, which means all paths in <math>C</math> are vertex-disjoint.

To show that the cover <math>C</math> has size <math>n-m</math>, we start with an empty cover and build it incrementally. To add a vertex <math>u</math> to the cover, we can either add it to an existing path, or create a new path of length zero starting at that vertex. The former case is applicable whenever either <math>(u,v) \in E</math> and some path in the cover starts at <math>v</math>, or <math>(v,u) \in E</math> and some path ends at <math>v</math>. The latter case is always applicable. In the former case, the total number of edges in the cover is increased by 1 and the number of paths stays the same; in the latter case the number of paths is increased and the number of edges stays the same. It is now clear that after covering all <math>n</math> vertices, the sum of the number of paths and edges in the cover is <math>n</math>. Therefore, if the number of edges in the cover is <math>m</math>, the number of paths is <math>n-m</math>.

===Maximum flow with vertex capacities=== thumb|right|Fig. 4.4.1. Transformation of a maximum flow problem with vertex capacities constraint into the original maximum flow problem by node splitting

Let <math>N = (V, E)</math> be a network. Suppose there is capacity at each node in addition to edge capacity, that is, a mapping <math>c: V\to \R^+,</math> such that the flow <math>f</math> has to satisfy not only the capacity constraint and the conservation of flows, but also the vertex capacity constraint

:<math> \sum_{i\in V} f_{iv} \le c(v) \qquad \forall v \in V \backslash \{s,t\}.</math>

In other words, the amount of flow passing through a vertex cannot exceed its capacity. To find the maximum flow across <math>N</math>, we can transform the problem into the maximum flow problem in the original sense by expanding <math>N</math>. First, each <math>v\in V</math> is replaced by <math>v_{\text{in}}</math> and <math>v_{\text{out}}</math>, where <math>v_{\text{in}}</math> is connected by edges going into <math>v</math> and <math>v_{\text{out}}</math> is connected to edges coming out from <math>v</math>, then assign capacity <math>c(v)</math> to the edge connecting <math>v_{\text{in}}</math> and <math>v_{\text{out}}</math> (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 number of paths from s to t=== Given a directed graph <math>G = (V, E)</math> and two vertices <math>s</math> and <math>t</math>, we are to find the maximum number of paths from <math>s</math> to <math>t</math>. This problem has several variants:

1. The paths must be edge-disjoint. This problem can be transformed to a maximum flow problem by constructing a network <math>N = (V, E)</math> from <math>G</math>, with <math>s</math> and <math>t</math> being the source and the sink of <math>N</math> respectively, and assigning each edge a capacity of <math>1</math>. In this network, the maximum flow is <math>k</math> iff there are <math>k</math> edge-disjoint paths.

2. The paths must be independent, i.e., vertex-disjoint (except for <math>s</math> and <math>t</math>). We can construct a network <math>N = (V, E)</math> from <math>G</math> with vertex capacities, where the capacities of all vertices and all edges are <math>1</math>. Then the value of the maximum flow is equal to the maximum number of independent paths from <math>s</math> to <math>t</math>.

3. In addition to the paths being edge-disjoint and/or vertex disjoint, the paths also have a length constraint: we count only paths whose length is exactly <math>k</math>, or at most <math>k</math>. Most variants of this problem are NP-complete, except for small values of <math>k</math>.<ref>{{Cite journal|last1=Itai|first1=A.|last2=Perl|first2=Y.|last3=Shiloach|first3=Y.|year=1982|title=The complexity of finding maximum disjoint paths with length constraints|journal=Networks|language=en|volume=12|issue=3|pages=277–286|doi=10.1002/net.3230120306|issn=1097-0037}}</ref>

=== Closure problem === {{Main|Closure problem}} A '''closure''' of a directed graph is a set of vertices ''C'', such that no edges leave ''C''. The '''closure problem''' is the task of finding the maximum-weight or minimum-weight closure in a vertex-weighted directed graph. It may be solved in polynomial time using a reduction to the maximum flow problem.

==Real world applications==

===Baseball elimination=== thumb|Construction of network flow for baseball elimination problem In the baseball elimination problem there are ''n'' teams competing in a league. At a specific stage of the league season, ''w''<sub>''i''</sub> is the number of wins and ''r''<sub>''i''</sub> is the number of games left to play for team ''i'' and ''r''<sub>ij</sub> 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<ref>{{Cite journal | last1 = Schwartz | first1 = B. L. | title = Possible Winners in Partially Completed Tournaments | doi = 10.1137/1008062 | journal = SIAM Review| jstor = 2028206| volume = 8 | issue = 3 | pages = 302–308 | year = 1966 | bibcode = 1966SIAMR...8..302S }}</ref> 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 {{math|''s'',''t'' ∈ ''V''}} being the source and the sink respectively. One adds a game node<sub>''ij''</sub> – which represents the number of plays between these two teams. We also add a team node for each team and connect each game node {{math|{{mset|''i'', ''j''}}}} with ''i'' < ''j'' to ''V'', and connects each of them from ''s'' by an edge with capacity ''r''<sub>''ij''</sub> – which represents the number of plays between these two teams. We also add a team node for each team and connect each game node {{math|{{mset|''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 {{math|''w''<sub>''k''</sub> + ''r''<sub>''k''</sub> – ''w''<sub>''i''</sub>}} is set to prevent team ''i'' from winning more than {{math|''w''<sub>''k''</sub> + ''r''<sub>''k''</sub>}}. Let ''S'' be the set of all teams participating in the league and let :<math>r(S - \{k\}) = \sum_{i,j \in \{S-\{k\}\} \atop i < j} r_{ij}</math>. 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.

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 {{math|''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''<sub>''i''</sub> as the source and node ''d''<sub>''i''</sub> as the destination node of flight ''i''. One also adds the following edges to ''E'': # An edge with capacity [0, 1] between ''s'' and each ''s''<sub>''i''</sub>. # An edge with capacity [0, 1] between each ''d''<sub>''i''</sub> and ''t''. # An edge with capacity [1, 1] between each pair of ''s''<sub>''i''</sub> and ''d''<sub>''i''</sub>. # An edge with capacity [0, 1] between each ''d''<sub>''i''</sub> and ''s''<sub>''j''</sub>, if source ''s''<sub>''j''</sub> is reachable with a reasonable amount of time and cost from the destination of flight ''i''. # 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.<ref name="ITA">{{cite book | author = Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein | title=Introduction to Algorithms, Second Edition | chapter = 26. Maximum Flow | year = 2001 | publisher = MIT Press and McGraw-Hill | isbn = 978-0-262-03293-3 | pages=643–668| title-link=Introduction to Algorithms }}</ref>

Another version of airline scheduling is finding the minimum needed crews to perform all the flights. To find an answer to this problem, a bipartite graph {{math|1={{var|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'', {{math|''i''∈''A''}} is connected to {{math|''j''∈''B''}}. A matching in {{mvar|G'}} induces a schedule for ''F'' and obviously maximum bipartite matching in this graph produces an airline schedule with minimum number of crews.<ref name="ITA"/> 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 {{mvar|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. # Add a source node {{mvar|s}} and add edges from it to every factory node {{mvar|f<sub>i</sub>}} with capacity {{mvar|p<sub>i</sub>}} where {{mvar|p<sub>i</sub>}} is the production rate of factory {{mvar|f<sub>i</sub>}}. # Add a sink node {{mvar|t}} and add edges from all villages {{mvar|v<sub>i</sub>}} to {{mvar|t}} with capacity {{mvar|d<sub>i</sub>}} where {{mvar|d<sub>i</sub>}} is the demand rate of village {{mvar|v<sub>i</sub>}}. Let ''G'' = (''V'', ''E'') be this new network. There exists a circulation that satisfies the demand if and only if : : {{math|Maximum flow value(''G'')}} <math> = \sum_{i \in v} d_i </math>. 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.

The problem can be extended by adding a lower bound on the flow on some edges.<ref>{{Cite web|url=https://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/flowext.pdf|title=Max-flow extensions: circulations with demands|last=Carl Kingsford}}</ref>

=== Image segmentation === thumb|Source image of size 8x8.|alt=|left|110x110px thumb|Network built from the bitmap. The source is on the left, the sink on the right. The darker an edge is, the bigger is its capacity. a<sub>i</sub> is high when the pixel is green, b<sub>i</sub> when the pixel is not green. The penalty p<sub>ij</sub> are all equal.<ref>{{Cite web|url=https://gitlab.com/francois.schwarzentruber/imagesegmentationwithmaxflow|title=Project imagesegmentationwithmaxflow, that contains the source code to produce these illustrations.|website=GitLab|language=en|url-status=dead|archive-url=https://web.archive.org/web/20191222173132/https://gitlab.com/francois.schwarzentruber/imagesegmentationwithmaxflow|archive-date=2019-12-22|access-date=2019-12-22}}</ref> In their book, Kleinberg and Tardos present an algorithm for segmenting an image.<ref>{{Cite web|url=https://www.pearson.com/us/higher-education/program/Kleinberg-Algorithm-Design/PGM319216.html |title=Algorithm Design|website=pearson.com|language=en|access-date=2019-12-21}}</ref> They present an algorithm to find the background and the foreground in an image. More precisely, the algorithm takes a bitmap as an input modelled as follows: ''a<sub>i</sub>'' ≥ 0 is the likelihood that pixel ''i'' belongs to the foreground, ''b<sub>i</sub>'' ≥ 0 in the likelihood that pixel ''i'' belongs to the background, and ''p<sub>ij</sub>'' is the penalty if two adjacent pixels ''i'' and ''j'' are placed one in the foreground and the other in the background. The goal is to find a partition (''A'', ''B'') of the set of pixels that maximize the following quantity

:<math>q(A, B) = \sum_{i \in A} a_i + \sum_{i \in B} b_i - \sum_{\begin{matrix}i, j \text{ adjacent} \\ |A \cap \{i, j\}| = 1 \end{matrix}} p_{ij}</math>,

Indeed, for pixels in ''A'' (considered as the foreground), we gain ''a<sub>i</sub>''; for all pixels in ''B'' (considered as the background), we gain ''b<sub>i</sub>''. On the border, between two adjacent pixels ''i'' and ''j'', we loose ''p<sub>ij</sub>''. It is equivalent to minimize the quantity

:<math>q'(A, B) = \sum_{i \in A} b_i + \sum_{i \in B} a_i + \sum_{\begin{matrix}i, j \text{ adjacent} \\ |A \cap \{i, j\}| = 1 \end{matrix}} p_{ij}</math>

because

:<math>q(A, B) = \sum_{i \in A\cup B} a_i + \sum_{i \in A\cup B} b_i - q'(A, B).</math>

thumb|Minimum cut displayed on the network (triangles VS circles).

We now construct the network whose nodes are the pixel, plus a source and a sink, see Figure on the right. We connect the source to pixel ''i'' by an edge of weight ''a<sub>i</sub>''. We connect the pixel ''i'' to the sink by an edge of weight ''b<sub>i</sub>''. We connect pixel ''i'' to pixel ''j'' with weight ''p<sub>ij</sub>''. Now, it remains to compute a minimum cut in that network (or equivalently a maximum flow). The last figure shows a minimum cut.

== Extensions == 1. In the '''minimum-cost flow problem''', each edge (''u'',v) also has a '''cost-coefficient''' ''a<sub>uv</sub>'' in addition to its capacity. If the flow through the edge is ''f<sub>uv</sub>'', then the total cost is ''a<sub>uv</sub>f<sub>uv</sub>.'' It is required to find a flow of a given size ''d'', with the smallest cost. In most variants, the cost-coefficients may be either positive or negative. There are various polynomial-time algorithms for this problem.

2. The maximum-flow problem can be augmented by '''disjunctive constraints''': a ''negative disjunctive constraint'' says that a certain pair of edges cannot simultaneously have a nonzero flow; a ''positive disjunctive constraints'' says that, in a certain pair of edges, at least one must have a nonzero flow. With negative constraints, the problem becomes strongly NP-hard even for simple networks. With positive constraints, the problem is polynomial if fractional flows are allowed, but may be strongly NP-hard when the flows must be integral.<ref>{{Cite journal|last1=Schauer|first1=Joachim|last2=Pferschy|first2=Ulrich|date=1 July 2013|title=The maximum flow problem with disjunctive constraints|journal=Journal of Combinatorial Optimization|language=en|volume=26|issue=1|pages=109–119|doi=10.1007/s10878-011-9438-7|issn=1382-6905|citeseerx=10.1.1.414.4496|s2cid=6598669}}</ref>

== References == {{reflist}}

==Further reading== * {{cite journal | author = Joseph Cheriyan and Kurt Mehlhorn | title = An analysis of the highest-level selection rule in the preflow-push max-flow algorithm | journal = Information Processing Letters | volume = 69 | year = 1999 | pages = 239–242 | doi = 10.1016/S0020-0190(99)00019-8 | issue = 5 | citeseerx = 10.1.1.42.8563 }} * {{cite journal | author = Daniel D. Sleator and Robert E. Tarjan | title = A data structure for dynamic trees | journal = Journal of Computer and System Sciences | volume = 26 | year = 1983 | issn = 0022-0000 | pages = 362–391 | doi = 10.1016/0022-0000(83)90006-5 | url = https://www.cs.cmu.edu/~sleator/papers/dynamic-trees.pdf | issue = 3 }} * {{cite book | author = Eugene Lawler | author-link = Eugene Lawler | title = Combinatorial Optimization: Networks and Matroids | chapter = 4. Network Flows | year = 2001 | publisher = Dover | isbn = 978-0-486-41453-9 | pages = 109–177}}

{{DEFAULTSORT:Maximum Flow Problem}} Category:Network flow problem Category:Computational problems in graph theory