Push–relabel maximum flow algorithm: Difference between revisions

Revision as of 21:52, 28 June 2019

Revision as of 21:54, 28 June 2019

Line 86:

===Correctness===

The algorithm maintains the condition that {{math|𝓁}} is a valid labeling during its execution. This can be proven true by examining the effects of the push and relabel operations on the label function {{math|𝓁}}. The relabel operation increases the label value by the associated minimum plus one which will always satisfy the {{math|𝓁(''u'') ≤ 𝓁(''v'') + 1}} constraint. The push operation can send flow from {{mvar|u}} to {{mvar|v}} if {{math|𝓁(''u'') {{=}} 𝓁(''v'') + 1}}. This may add {{math|(''v'', ''u'')}} to {{math|''G''_''f''&nbsp;}} and may delete {{math|(''u'', ''v'')}} from {{math|''G''_''f''&nbsp;}}. The addition of {{math|(''v'', ''u'')}} to {{math|''G''_''f''&nbsp;}} will not affect the valid labeling since {{math|𝓁(''v'') {{=}} 𝓁(''u'') -− 1}}. The deletion of {{math|(''u'', ''v'')}} from {{math|''G''_''f''&nbsp;}} removes the corresponding constraint since the valid labeling property {{math|𝓁(''u'') ≤ 𝓁(''v'') + 1}} only applies to residual arcs in {{math|''G''_''f''&nbsp;}}.<ref name="goldberg88"/>

If a preflow {{mvar|f}} and a valid labeling {{math|𝓁}} for {{mvar|f}} exists then there is no augmenting path from {{mvar|s}} to {{mvar|t}} in the residual graph {{math|''G''_''f''&nbsp;}}. This can be proven by contradiction based on inequalities which arise in the labeling function when supposing that an augmenting path does exist. If the algorithm terminates, then all nodes in {{math|''V'' \ {{(}}''s'', ''t''{{)}}}} are not active. This means all {{math|''v'' ∈ ''V'' \ {{(}}''s'', ''t''{{)}}}} have no excess flow, and with no excess the preflow {{mvar|f}} obeys the flow conservation constraint and can be considered a normal flow. This flow is the maximum flow according to the [[max-flow min-cut theorem]] since there is no augmenting path from {{mvar|s}} to {{mvar|t}}.<ref name="goldberg88"/>

Line 95:

In order to bound the time complexity of the algorithm, we must analyze the number of push and relabel operations which occur within the main loop. The numbers of relabel, saturating push and nonsaturating push operations are analyzed separately.

In the algorithm, the relabel operation can be performed at most {{math|(2{{!}}&nbsp;''V''&nbsp;{{!}} − 1)({{!}}&nbsp;''V''&nbsp;{{!}} − 2) < 2{{!}}&nbsp;''V''&nbsp;{{!}}²}} times. This is because the labeling {{math|𝓁(''u'')}} value for any node ''u'' can never decrease, and the maximum label value is at most {{math|2{{!}}&nbsp;''V''&nbsp;{{!}} -− 1}} for all nodes. This means the relabel operation could potentially be performed {{math|2{{!}}&nbsp;''V''&nbsp;{{!}} -− 1 }} times for all nodes {{math|''V'' \ {{(}}''s'', ''t''{{)}}}} (i.e. {{math|{{!}}&nbsp;''V''&nbsp;{{!}} -− 2}}). This results in a bound of {{math|''O''(''V''^&nbsp;2)}} for the relabel operation.

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.

In sum, the algorithm executes {{math|''O''(''V''^&nbsp;2)}} relabels, {{math|''O''(''VE'')}} saturating pushes and {{math|''O''(''V''^&nbsp;2''E'')}} nonsaturating pushes. Data structures can be designed to pick and execute an applicable operation in {{math|''O''(1)}} time. Therefore, the time complexity of the algorithm is {{math|''O''(''V''^&nbsp;2''E'')}}.<ref name="clrs26"/><ref name="goldberg88"/>

Line 410:

{{reflist|2|refs=

<ref name="clrs26">{{Cite book | isbn = 978-0262032933 | title = Introduction to Algorithms | edition = 2nd | last1 = Cormen | first1 = T. H. | authorlink1 = Thomas H. Cormen | year = 2001 | publisher = The MIT Press | last2 = Leiserson | first2 = C. E. | authorlink2 = Charles E. Leiserson | last3 = Rivest | first3 = R. L. | authorlink3 = Ron Rivest | last4 = Stein | first4 = C. | authorlink4 = Clifford Stein | chapter = §26 Maximum flow | pages = 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}}</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.}}</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>

Line 421:

<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.}}</ref>

}}