Push–relabel maximum flow algorithm: Difference between revisions

Revision as of 21:12, 1 December 2020

Latest revision as of 19:05, 30 July 2025

(26 intermediate revisions by 19 users not shown)

Line 1:

{{Short description|Algorithm in mathematical optimization}}

{{MOS|article|date=July 2025| [[MOS:FORMULA]] - avoid mixing {{tag|math}} and {{tl|math}} in the same expression}}

In [[mathematical optimization]], the '''push–relabel algorithm''' (alternatively, '''preflow–push algorithm''') is an algorithm for computing [[maximum flow]]s in a [[flow network]]. The name "push–relabel" comes from the two basic operations used in the algorithm. Throughout its execution, the algorithm maintains a "preflow" and gradually converts it into a maximum flow by moving flow locally between neighboring nodes using ''push'' operations under the guidance of an admissible network maintained by ''relabel'' operations. In comparison, the [[Ford–Fulkerson algorithm]] performs global augmentations that send flow following paths from the source all the way to the sink.<ref name="clrs26"/>

The push–relabel algorithm is considered one of the most efficient maximum flow algorithms. The generic algorithm has a [[strongly polynomial]] {{math|''O''(''V''^&nbsp;2''E'')}} time complexity, which is asymptotically more efficient than the {{math|''O''(''VE''^&nbsp;2)}} [[Edmonds–Karp algorithm]].<ref name="goldberg86"/> Specific variants of the algorithms achieve even lower time complexities. The variant based on the highest label node selection rule has {{math|''O''(''V''^&nbsp;2{{sqrt|''E''}})}} time complexity and is generally regarded as the benchmark for maximum flow algorithms.<ref name="ahuja97"/><ref name="goldberg08"/> Subcubic {{math|''O''(''VE''log(''V''^&nbsp;2/''E''))}} time complexity can be achieved using [[Link-cut tree|dynamic trees]],<ref name="goldberg86"/> although in practice it is less efficient.<ref{{reference nameneeded|date="goldberg86"/>December 2024}}

The push–relabel algorithm has been extended to compute [[minimum cost flow]]s.<ref name="goldberg97"/> The idea of distance labels has led to a more efficient augmenting path algorithm, which in turn can be incorporated back into the push–relabel algorithm to create a variant with even higher empirical performance.<ref name="goldberg08"/><ref name="ahuja91"/>

Line 9 ⟶ 11:

The concept of a preflow was originally designed by [[Alexander V. Karzanov]] and was published in 1974 in Soviet Mathematical Dokladi 15. This pre-flow algorithm also used a push operation; however, it used distances in the auxiliary network to determine where to push the flow instead of a labeling system.<ref name="goldberg86"/><ref name="goldberg2014"/>

The push-relabel algorithm was designed by [[Andrew V. Goldberg]] and [[Robert Tarjan]]. The algorithm was initially presented in November 1986 in STOC '86: Proceedings of the eighteenth annual ACM symposium on Theory of computing, and then officially in October 1988 as an article in the Journal of the ACM. Both papers detail a generic form of the algorithm terminating in {{math|''O''(''V''^&nbsp;2''E'')}} along with a {{math|''O''(''V''^&nbsp;3)}} sequential implementation, a {{math|''O''(''VE''&nbsp;log(''V''^&nbsp;2/''E''))}} implementation using dynamic trees, and parallel/distributed implementation.<ref name="goldberg86"/><ref name="goldberg88"/> AAs explained in ,<ref name="amo93"/> Goldberg-Tarjan introduced distance labels by incorporating them into the parallel maximum flow algorithm of Yossi Shiloach and [[Uzi Vishkin]].<ref name="sv82"/>

==Concepts==

Line 17 ⟶ 19:

Let:

*{{math|''G'' {{=}} (''V'', ''E'')}} be a ''network'' with ''capacity function'' {{math|''c'': ''V'' × ''V'' → ℝ<math>\mathbb{R}</math>_∞}},

*{{math|''F'' {{=}} (''G'', ''c'', ''s'', ''t'')}} a ''flow network'', where {{math|''s'' ∈ ''V''}} and {{math|''t'' ∈ ''V''}} are chosen ''source'' and ''sink'' vertices respectively,

*{{math|''f'' : ''V'' × ''V'' → ℝ<math>\mathbb{R}</math>}} denote a [[Flow network#Flows|''pre-flow'']] in {{mvar|F}},

*{{math|''x''_''f'' : ''V'' → ℝ<math>\mathbb{R}</math>}} denote the ''excess'' function with respect to the flow {{mvar|f}}, defined by {{math|''x''_''f'' (''u'') {{=}} ∑Σ_{''v'' ∈ ''V''} ''f'' (''v'', ''u'') − ∑Σ_{''v'' ∈ ''V''} ''f'' (''u'', ''v'')}},

*{{math|''c''_''f'' : ''V'' × ''V'' → ℝ<math>\mathbb{R}</math>_∞}} denote the ''residual capacity function'' with respect to the flow {{mvar|f}}, defined by {{math|''c''_''f''&nbsp;(''e'') {{=}} ''c''(''e'') − ''f''&nbsp;(''e'')}},

*{{math|''E''_''f'' ⊂ ''E''}} being the edges where {{math|''f'' < ''c''}},

and

*{{math|''G''_''f'' (''V'', ''E''_''f''&nbsp;)}} denote the [[Flow network#Residuals|''residual network'']] of {{mvar|G}} with respect to the flow {{mvar|f}}.

The push–relabel algorithm uses a nonnegative integer valid '''labeling function''' which makes use of ''distance labels'', or ''heights'', on nodes to determine which arcs should be selected for the push operation. This labeling function is denoted by {{math|𝓁 : ''V'' → ℕ<math>\mathbb{N}</math>}}. This function must satisfy the following conditions in order to be considered valid:

:'''Valid labeling''':

Line 37 ⟶ 40:

An arc {{math|(''u'', ''v'') ∈ ''E''_''f''}}&nbsp; is called '''admissible''' if {{math|𝓁(''u'') {{=}} 𝓁(''v'') + 1}}. The '''admissible network''' {{math|''G̃''_''f'' (''V'', ''Ẽ''_''f''&nbsp;)}} is composed of the set of arcs {{math|''e'' ∈ ''E''_''f''}}&nbsp; that are admissible. The admissible network is acyclic.

For a fixed flow {{math|''f''}}, a vertex {{math|''v ∉ ''{''s, t''} }} is called '''active''' if it has positive excess with respect to {{math|''f''}}, i.e., {{math|''x''_''f'' (''u'') > 0}}.

===Operations===

Line 42 ⟶ 47:

====Initialization====

The algorithm starts by creating a residual graph, initializing the preflow values to zero and performing a set of saturating push operations on residual arcs exiting the source, {{math|(''s'', ''v'')}} exiting the source, where {{math|''v'' ∈ ''V'' \ {{(}}''s''{{)}}}}. Similarly, the labels are initialized such that the label at the source is the number of nodes in the graph, {{math|𝓁(''s'') {{=}} {{!}}&nbsp;''V''&nbsp;{{!}}}}, and all other nodes are given a label of zero. Once the initialization is complete the algorithm repeatedly performs either the push or relabel operations against active nodes until no applicable operation can be performed.

====Push====

Line 58 ⟶ 63:

====Relabel====

The relabel operation applies on an active node {{mvar|u}} which is neither the source nor the sink without any admissible out-arcs in {{math|''G_f''}}. It modifies {{math|𝓁(''u'')}} to be the minimum value such that an admissible out-arc is created. Note that this always increases {{math|𝓁(''u'')}} and never creates a steep arc, which is an arc {{math|(''u'', ''v'')}} such that {{math|''c''_''f''&nbsp;(''u'', ''v'') > 0}}, and {{math|𝓁(''u'') > 𝓁(''v'') + 1}}.

relabel(u):

Line 98 ⟶ 103:

Each saturating push on an admissible arc {{math|(''u'', ''v'')}} removes the arc from {{math|''G''_''f''&nbsp;}}. For the arc to be reinserted into {{math|''G''_''f''&nbsp;}} for another saturating push, {{mvar|v}} must first be relabeled, followed by a push on the arc {{math|(''v'', ''u'')}}, then {{mvar|u}} must be relabeled. In the process, {{math|𝓁(''u'')}} increases by at least two. Therefore, there are {{math|''O''(''V'')}} saturating pushes on {{math|(''u'', ''v'')}}, and the total number of saturating pushes is at most {{math|2{{!}}&nbsp;''V''&nbsp;{{!}}{{!}}&nbsp;''E''&nbsp;{{!}}}}. This results in a time bound of {{math|''O''(''VE'')}} for the saturating push operations.

Bounding the number of nonsaturating pushes can be achieved via a [[Potential method|potential argument]]. We use the potential function {{math|Φ {{=}} ∑Σ_{[''u'' ∈ ''V'' ∧ ''x''_''f''&nbsp;(''u'') > 0]} 𝓁(''u'')}} (i.e. {{math|Φ}} is the sum of the labels of all active nodes). It is obvious that {{math|Φ}} is {{math|0}} initially and stays nonnegative throughout the execution of the algorithm. Both relabels and saturating pushes can increase {{math|Φ}}. However, the value of {{math|Φ}} must be equal to 0 at termination since there cannot be any remaining active nodes at the end of the algorithm's execution. This means that over the execution of the algorithm, the nonsaturating pushes must make up the difference of the relabel and saturating push operations in order for {{math|Φ}} to terminate with a value of 0.

The relabel operation can increase {{math|Φ}} by at most {{math|(2{{!}}&nbsp;''V''&nbsp;{{!}} − 1)({{!}}&nbsp;''V''&nbsp;{{!}} − 2)}}. A saturating push on {{math|(''u'', ''v'')}} activates {{mvar|v}} if it was inactive before the push, increasing {{math|Φ}} by at most {{math|2{{!}}&nbsp;''V''&nbsp;{{!}} − 1}}. Hence, the total contribution of all saturating pushes operations to {{math|Φ}} is at most {{math|(2{{!}}&nbsp;''V''&nbsp;{{!}} − 1)(2{{!}}&nbsp;''V''&nbsp;{{!}}{{!}}&nbsp;''E''&nbsp;{{!}})}}. A nonsaturating push on {{math|(''u'', ''v'')}} always deactivates {{mvar|u}}, but it can also activate {{mvar|v}} as in a saturating push. As a result, it decreases {{math|Φ}} by at least {{math|𝓁(''u'') − 𝓁(''v'') {{=}} 1}}. Since relabels and saturating pushes increase {{math|Φ}}, the total number of nonsaturating pushes must make up the difference of {{math|(2{{!}}&nbsp;''V''&nbsp;{{!}} − 1)({{!}}&nbsp;''V''&nbsp;{{!}} − 2) + (2{{!}}&nbsp;''V''&nbsp;{{!}} − 1)(2{{!}}&nbsp;''V''&nbsp;{{!}}{{!}}&nbsp;''E''&nbsp;{{!}}) ≤ 4{{!}}&nbsp;''V''&nbsp;{{!}}²{{!}}&nbsp;''E''&nbsp;{{!}}}}. This results in a time bound of {{math|''O''(''V''^&nbsp;2''E'')}} for the nonsaturating push operations.

Line 178 ⟶ 183:

push(u, v)

'''let''' current-arc[u] point to the next neighbor of u

Finding the next admissible edge to push on has <math>O(1)</math> [[amortized complexity]]. The current-arc pointer only moves to the next neighbor when the edge to the current neighbor is saturated or non-admissible, and neither of these two properties can change until the active node <math>u</math> is relabelled. Therefore, when the pointer runs off, there are no admissible unsaturated edges and we have to relabel the active node <math>u</math>, so having moved the pointer <math>O(V)</math> times is paid for by the <math>O(V)</math> relabel operation.<ref name="goldberg88" />

===Active node selection rules===

Line 369 ⟶ 375:

# if such a push is possible at all.

min_height = ∞

for v in xrangerange(n):

if C[u][v] - F[u][v] > 0:

min_height = min(min_height, height[v])

Line 408 ⟶ 414:

== References ==

{{reflist|2|refs=

<ref name="clrs26">{{Cite book | isbn = 978-0262032933 | title = Introduction to Algorithms | edition = 2nd | last1 = Cormen | first1 = T. H. | authorlink1author-link1 = Thomas H. Cormen | year = 2001 | publisher = The MIT Press | last2 = Leiserson | first2 = C. E. | authorlink2author-link2 = Charles E. Leiserson | last3 = Rivest | first3 = R. L. | authorlink3author-link3 = Ron Rivest | last4 = Stein | first4 = C. | authorlink4author-link4 = Clifford Stein | chapter = §26 Maximum flow | pages = [https://archive.org/details/introductiontoal00corm_691/page/n665 643]–698| title-link = Introduction to Algorithms }}</ref>

<ref name="goldberg86">{{cite book|doi=10.1145/12130.12144|chapter=A new approach to the maximum flow problem|title=Proceedings of the eighteenth annual ACM symposium on Theory of computing – STOC '86|pages=136|year=1986|last1=Goldberg|first1=A V|last2=Tarjan|first2=R E|isbn=978-0897911931|s2cid=14492800}}</ref>

<ref name="goldberg88">{{cite journal|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|last1=Goldberg|first1=Andrew V.|last2=Tarjan|first2=Robert E.|s2cid=52152408|doi-access=free}}</ref>

<ref name="sv82">{{cite journal|doi=10.1016/0196-6774(82)90013-X|title=An O(n2log n) parallel max-flow algorithm|journal=Journal of Algorithms|volume=3|issue=2|pages=128–146|year=1982|last1=Shiloach|first1=Yossi|last2=Vishkin|first2=Uzi}}</ref>

<ref name="cheriyan88">{{cite book|doi=10.1007/3-540-50517-2_69|chapter=Analysis of preflow push algorithms for maximum network flow|title=Foundations of Software Technology and Theoretical Computer Science|volume=338|pages=30|series=Lecture Notes in Computer Science|year=1988|last1=Cheriyan|first1=J.|last2=Maheshwari|first2=S. N.|isbn=978-3-540-50517-4}}</ref>

<ref name="derigs89">{{cite journal|doi=10.1007/BF01415937|title=Implementing Goldberg's max-flow-algorithm ? A computational investigation|journal=ZOR Zeitschrift für Operations Research Methods and Models of Operations Research|volume=33|issue=6|pages=383|year=1989|last1=Derigs|first1=U.|last2=Meier|first2=W.|s2cid=39730584}}</ref>

<ref name="ahuja91">{{cite journal|doi=10.1002/1520-6750(199106)38:3<413::AID-NAV3220380310>3.0.CO;2-J|title=Distance-directed augmenting path algorithms for maximum flow and parametric maximum flow problems|journal=Naval Research Logistics|volume=38|issue=3|pages=413|year=1991|last1=Ahuja|first1=Ravindra K.|last2=Orlin|first2=James B.|citeseerx=10.1.1.297.5698}}</ref>

<ref name="amo93">{{Cite book | isbn = 978-0136175490 | title = Network Flows: Theory, Algorithms, and Applications | edition = 1st | last1 = Ahuja | first1 = R. K. | year = 1993 | publisher = Prentice Hall | last2 = Magnanti | first2 = T. L. | last3 = Orlin | first3 = J. B. | pages = }}</ref>

<ref name="cherkassky95">{{cite book|doi=10.1007/3-540-59408-6_49|chapter=On implementing push-relabel method for the maximum flow problem|title=Integer Programming and Combinatorial Optimization|volume=920|pages=157|series=Lecture Notes in Computer Science|year=1995|last1=Cherkassky|first1=Boris V.|last2=Goldberg|first2=Andrew V.|isbn=978-3-540-59408-6|citeseerx=10.1.1.150.3609}}</ref>

<ref name="ahuja97">{{cite journal|doi=10.1016/S0377-2217(96)00269-X|title=Computational investigations of maximum flow algorithms|journal=European Journal of Operational Research|volume=97|issue=3|pages=509|year=1997|last1=Ahuja|first1=Ravindra K.|last2=Kodialam|first2=Murali|last3=Mishra|first3=Ajay K.|last4=Orlin|first4=James B.|citeseerx=10.1.1.297.2945}}</ref>

<ref name="goldberg97">{{cite journal|doi=10.1006/jagm.1995.0805|title=An Efficient Implementation of a Scaling Minimum-Cost Flow Algorithm|journal=Journal of Algorithms|volume=22|pages=1–29|year=1997|last1=Goldberg|first1=Andrew V}}</ref>

<ref name="goldberg08">{{cite book|doi=10.1007/978-3-540-87744-8_39|chapter=The Partial Augment–Relabel Algorithm for the Maximum Flow Problem|title=Algorithms – ESA 2008|volume=5193|pages=466–477|series=Lecture Notes in Computer Science|year=2008|last1=Goldberg|first1=Andrew V.|isbn=978-3-540-87743-1|citeseerx=10.1.1.150.5103}}</ref>

<ref name="goldberg2014">{{cite journal|doi=10.1145/2628036|title=Efficient maximum flow algorithms|journal=Communications of the ACM|volume=57|issue=8|pages=82|year=2014|last1=Goldberg|first1=Andrew V.|last2=Tarjan|first2=Robert E.|s2cid=17014879}}</ref>

}}

{{optimization algorithms|combinatorial|state=expanded}}

{{DEFAULTSORT:Push-relabel maximum flow algorithm}}

[[Category:Network flow problem]]

[[Category:Graph algorithms]]

[[Category:Articles with example C code]]

[[Category:Articles with example Python (programming language) code]]