Push–relabel maximum flow algorithm: Difference between revisions

Revision as of 01:25, 30 April 2021

Revision as of 05:47, 27 October 2021

Line 17:

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 99:

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.