Ahuja-Orlin: Difference between revisions

From Algowiki
Jump to navigation Jump to search
 
(34 intermediate revisions by the same user not shown)
Line 6: Line 6:


== Abstract View ==
== Abstract View ==
'''Auxiliary data:'''
# A nonnegative integral value <math>d(v)</math> for each node <math>v\in V</math>.
# Each node <math>v\in V\setminus\{t\}</math> has a '''current arc''', which may be implemented as an iterator on the list of outgoing arcs of <math>v</math>.
# A [[Sets and sequences#Stacks and queues|stack]] <math>S</math> of nodes.


'''Invariant:'''
'''Invariant:'''
After <math>i \ge 0</math> iterations:
After <math>i \ge 0</math> iterations:
# The flow <math>f</math> is a fleasible flow.
# The flow <math>f</math> is a feasible flow.
# If all upper bounds are integral, <math>f</math> is integral as well.
# If all upper bounds are integral, <math>f</math> is integral as well.
# There is a [[Basic flow definitions#Valid distance labeling|valid distance labeling]] <math>d</math> with respect to <math>f</math>.
# The values <math>d(\cdot)</math> are a [[Basic flow definitions#Valid distance labeling|valid distance labeling]] with respect to <math>f</math>.
# Each node <math>v\in V\setminus\{t\}</math> has a '''current arc''', which is either void or one of the outgoing arcs of <math>v</math>.
# The current arc of a node <math>v\in V\setminus\{s,t\}</math> is either void or one of the outgoing arcs of <math>v</math>. No admissible outgoing arc of <math>v</math> precedes the current arc of <math>v</math>.
# Stack <math>S</math> contains a '''current flow-augmenting path''' with respect to <math>f</math>. This path starts with <math>s</math> and ends at an arbitrary node of <math>G</math>. Each arc on this path is admissible and the current arc of its tail node.
# Stack <math>S</math> contains a cycle-free [[Basic flow definitions#Flow-augmenting paths and saturated arcs|flow-augmenting path]] with respect to <math>f</math>. This path starts with <math>s</math> and ends at an arbitrary node of <math>G</math>. Each arc on this path is admissible and the current arc of its tail node.


'''Variant:'''
'''Variant:'''
At least one of the following actions will take place in the current iteration:
One of the following actions will take place in the current iteration:
# An arc is appended to the current path.
# An arc is appended to the current path (when going forward in the [[Depth-first search|depth-first search]] for an [[Basic flow definitions#Flow-augmenting paths and saturated arcs|augmenting path]]).
# At least one arc is [[Basic flow definitions|saturated]].
# At least one arc is [[Basic flow definitions|saturated]] (when [[Basic flow definitions#Augmenting along a path|augmenting along the path up to saturation]]).
# The distance label of some node is increased.
# The distance label of some node is increased (when going backward in the [[Depth-first search|depth-first search]] for an [[Basic flow definitions#Flow-augmenting paths and saturated arcs|augmenting path]]).


'''Break condition:''' It is <math>d(s)\geq n</math>, where <math>n=|V|</math>,
'''Break condition:''' It is <math>d(s)=n</math>, where <math>n=|V|</math>,


== Induction basis ==
== Induction basis ==
Line 27: Line 32:
'''Abstract view:'''
'''Abstract view:'''
# We start with some feasible flow, for example, the zero flow.
# We start with some feasible flow, for example, the zero flow.
# Also, we start with some [[Basic flow definitions|valid distance labeling]].
# Also, we start with some [[Basic flow definitions#Valid distance labeling|valid distance labeling]] with respect to the initial flow.
# Stack <math>S</math> is initialized so as to contain <math>s</math> and no other node.
# Stack <math>S</math> is initialized so as to contain <math>s</math> and no other node.
# The current arc of each node <math>v\in V</math> is reset to be the very first outgoing arc of <math>v</math>.
# The current arc of each node <math>v\in V</math> is reset to be the very first outgoing arc of <math>v</math>.


'''Implementation:'''
'''Implementation''' of step 2 in case <math>f</math> is initialized as the zero flow:
# For all <math>a \in A</math>, set <math>f(a):=0. </math>  
A [[Breadth-first search|BFS]] is run on the [[Basic graph definitions#Transpose|transpose]] of <math>G</math> with start node <math>t</math>; the resulting distances are the <math>d</math>-labels.
# Run a [[Breadth-first search|BFS]] on the [[Basic graph definitions|transpose]] of <math>G</math> with start node <math>t</math> and unit arc lengths; the resulting distances are the <math>d</math>-labels.
# Create <math>S</math> and push <math>s</math> onto <math>S</math>.
# Reset the current arcs.


'''Proof:'''
'''Proof of the implementation:'''
Obvious.
Clearly, it is <math>d(t)=0</math>, so it remains to show <math>d(v)\leq d(w)+1</math> for each arc <math>a\in A</math>.
If <math>f</math> is the zero flow, the arcs of the residual network <math>G_f</math> are exactly the arcs of <math>G</math>. So, the claim follows immediately from the [[Basics of shortest paths#Valid distance property|valid distance property]].


== Induction step ==
== Induction step ==
Line 45: Line 48:
# Let <math>v</math> be the top element of <math>S</math>, that is, the endnode of the corresponding path.
# Let <math>v</math> be the top element of <math>S</math>, that is, the endnode of the corresponding path.
# If <math>v=t</math>:
# If <math>v=t</math>:
## Augment the current flow along the path corresponding to <math>S</math>.
## [[Basic flow definitions#Augmenting along a path|Augment]] the current flow along the path corresponding to <math>S</math> up to saturation.
## Remove all nodes but <math>s</math> from <math>S</math>.
## Remove all nodes but <math>s</math> from <math>S</math>.
# Otherwise:
# Otherwise:
## While the current arc of <math>v</math> is not void and not [[Basic flow definitions#Valid distance labeling|admissible]] or points to <math>s</math>: Move the current arc one step forward.
## While the current arc of <math>v</math> is not void and not [[Basic flow definitions#Valid distance labeling|admissible]] or points to <math>s</math>: Move the current arc one step forward.
## If the current arc is void: Set <math>d(v):=\tilde{d}+1</math>, where <math>\tilde{d}</math> denotes the minimum value <math>d(w)</math> over all outgoing arcs <math>(v,w)</math> of <math>v</math> in the residual network.
## If the current arc of <math>v</math> is now void:
### Set <math>d(v):=\tilde{d}+1</math>, where <math>\tilde{d}</math> denotes the minimum value <math>d(w)</math> over all outgoing arcs <math>(v,w)</math> of <math>v</math> in the residual network.
### Reset the current arc of <math>v</math> to the beginning of the list of outgoing arcs of <math>v</math>.
### Remove <math>v</math> from <math>S</math>.
## Otherwise, that is, if the current arc is some arc <math>(v,w)</math>: Push <math>w</math> on <math>S</math>.
## Otherwise, that is, if the current arc is some arc <math>(v,w)</math>: Push <math>w</math> on <math>S</math>.


'''Proof:'''
'''Proof:'''
The variant and points 1, 2,  and 4 are obvious. For point 5, note that step 2.3.1 skips all non-admissible arcs, so step 2.3.3 is only applied to admissible arcs. Finally, point 3 of the invariant follows from the maximally conservative increase of <math>d(v)</math> in step 3.2.
The variant, points 1, 2,  and 5 of the invariant, and the first sentence of point 4 of the invariant are obvious. For the second sentence of point 4, note that no admissible arc of <math>v</math> is skipped when the current arc is moved forward, and the current arc is reset whenever outgoing arcs may become admissible due to an increase of <math>d(v)</math>. Finally, point 3 of the invariant follows from the conservative increase of <math>d(v)</math> in step 3.2.


== Correctness ==
== Correctness ==


First we show that the flow is maximum when the break condition applies. Due to the [[Max-flow min-cut|max-flow min-cut theorem]], it suffices to show that, in this moment, there is no more flow augmenting <math>(s,t)</math>-path. However, such a path would have at most <math>n-1</math> arcs, and for each arc <math>(v,w)</math> on this path, it is <math>d(v)\leq d(w)+1</math>. This implies <math>d(s)-d(t)=d(s)\leq n-1</math>, which contradicts the break condition.
First we show that the flow is maximum when the break condition applies. Due to the [[Max-flow min-cut|max-flow min-cut theorem]], it suffices to show that, in this moment, there is no more flow-augmenting <math>(s,t)</math>-path. However, such a path would have at most <math>n-1</math> arcs, and for each arc <math>(v,w)</math> on this path, it is <math>d(v)\leq d(w)+1</math>. This implies <math>d(s)-d(t)=d(s)\leq n-1</math>, which contradicts the break condition.


It remains to show that the algorithm indeed terminates. This is proved by the following complexity bound.
It remains to show that the algorithm indeed terminates. This is proved by the following complexity considerations.


== Complexity ==
== Complexity ==
Line 69: Line 75:
First we show that no distance label <math>d(v)</math> may become higher than <math>n</math> (in particular, the total number of executions of step 3.2 over all iterations is in <math>\mathcal{O}(n^2)</math>).
First we show that no distance label <math>d(v)</math> may become higher than <math>n</math> (in particular, the total number of executions of step 3.2 over all iterations is in <math>\mathcal{O}(n^2)</math>).


To see that, recall <math>d(s)<n</math> from the break condition. Whenever the distance label <math>d(v)</math> of a node <math>v\in V</math> is increased, <math>v</math> is the endnode of the current path, which consists solely of admissible arcs. Due to the definition of admissible arcs, it is <math>d(v)\leq d(s)</math> immediately before the current iteration (equality only if <math>v=s</math>). Let <math>(v,w)</math> be an arc such that <math>\tilde{d}=d(w)</math>. For the same reason, it is <math>d(w)<d(s)</math>, which implies <math>d(v)\leq d(s)</math> immediately after the current iteration.
To see that, recall that <math>d(s)<n</math> as long as the break condition is not fulfilled. Whenever the distance label <math>d(v)</math> of a node <math>v\in V</math> is increased, <math>v</math> is the endnode of the current path, which consists solely of admissible arcs. Due to the definition of admissible arcs, it is <math>d(v)\leq d(s)</math> immediately before the current iteration (equality only if <math>v=s</math>). Let <math>(v,w)</math> be an arc such that <math>\tilde{d}=d(w)</math>, in particular, it is <math>w\neq s</math>. For the same reason, it is <math>d(w)<d(s)</math>, which implies <math>d(v)\leq d(s)</math> immediately after the current iteration.


Now we know <math>d(u)\leq n</math> for all nodes <math>u\in V</math>. Next we consider an arbitrary but fixed arc <math>(v,w)\in A</math>. Suppose <math>(v,w)</math> has ben [[Basic flow definitions|saturated]] at least twice during the algorithm. In both iterations, <math>(v,w)</math> is admissible, which means <math>d(v)>d(w)</math>. However, in the meantime, some flow must have been sent back from <math>w</math> to <math>v</math>, which implies <math>d(w)>d(v)</math>. In that intermediate iteration. As distance labels are non-decreasing, <math>d(v)</math> must have been increased between any two iterations in which <math>(v,w)</math> is saturated. In summary, each arc is saturated only <math>\mathcal{O}(n)</math> times.
Now we know <math>d(u)\leq n</math> for all nodes <math>u\in V</math>. Next we consider an arbitrary but fixed arc <math>(v,w)\in A</math>. Suppose <math>(v,w)</math> has ben [[Basic flow definitions|saturated]] at least twice during the algorithm. In both iterations, <math>(v,w)</math> is admissible, which means <math>d(v)>d(w)</math>. However, in the meantime, some flow must have been sent back from <math>w</math> to <math>v</math>, which implies <math>d(w)>d(v)</math> in that intermediate iteration. As distance labels are non-decreasing, <math>d(v)</math> must have been increased between any two iterations in which <math>(v,w)</math> is saturated. In summary, each arc is saturated only <math>\mathcal{O}(n)</math> times.


In each execution of step 2.1+2.2, at least one arc is saturated, so the total number of executions of step 2.1+2.2 is in <math>\mathcal{O}(nm)</math>. The path contains at most <math>n-1</math> arcs, so the total asymptotic complexity for all executions of step 2.1+2 is in <math>\mathcal{O}(n^2m)</math>.
In each execution of step 2.1 of the induction step, at least one arc is saturated, so the total number of executions of step 2.1+2.2 is in <math>\mathcal{O}(nm)</math>. The path contains at most <math>n-1</math> arcs, so the total asymptotic complexity for all executions of step 2.1+2 is in <math>\mathcal{O}(n^2m)</math>.


Finally, the sequence of outgoing arcs is passed once for each node in step 3.1, so the total asymptotic complexity of all exections of step 3.1 over all iterations is linear in the number of arcs.
Finally, the sequence of outgoing arcs is passed once for each node in step 3.1 between two increases of <math>d(v)</math>, so the total asymptotic complexity of all executions of step 3.1 over all iterations is in <math>\mathcal{O}(n\cdot m)</math>.


== Remark ==
== Remark ==


This algorithm may be seen as a "lazy" variant on [[Edmonds-Karp]]. In fact, the most expensive step there is the computation of a flow-augmenting <math>(s,t)</math>-path. This task amounts to computing the true distance from every node to <math>t</math>. A valid distance labeling may be seen as "lazily evaluated" true distances.
This algorithm may be seen as a "lazy" variant on [[Edmonds-Karp]]. In fact, the most expensive step there is the computation of a shortest flow-augmenting <math>(s,t)</math>-path. This task amounts to computing the true distance from every node to <math>t</math>. A valid distance labeling may be seen as "lazily evaluated" true distances.

Latest revision as of 07:59, 30 November 2015

General Information

Algorithmic problem: Max-flow problems (standard version)

Type of algorithm: loop

Abstract View

Auxiliary data:

  1. A nonnegative integral value [math]\displaystyle{ d(v) }[/math] for each node [math]\displaystyle{ v\in V }[/math].
  2. Each node [math]\displaystyle{ v\in V\setminus\{t\} }[/math] has a current arc, which may be implemented as an iterator on the list of outgoing arcs of [math]\displaystyle{ v }[/math].
  3. A stack [math]\displaystyle{ S }[/math] of nodes.

Invariant: After [math]\displaystyle{ i \ge 0 }[/math] iterations:

  1. The flow [math]\displaystyle{ f }[/math] is a feasible flow.
  2. If all upper bounds are integral, [math]\displaystyle{ f }[/math] is integral as well.
  3. The values [math]\displaystyle{ d(\cdot) }[/math] are a valid distance labeling with respect to [math]\displaystyle{ f }[/math].
  4. The current arc of a node [math]\displaystyle{ v\in V\setminus\{s,t\} }[/math] is either void or one of the outgoing arcs of [math]\displaystyle{ v }[/math]. No admissible outgoing arc of [math]\displaystyle{ v }[/math] precedes the current arc of [math]\displaystyle{ v }[/math].
  5. Stack [math]\displaystyle{ S }[/math] contains a cycle-free flow-augmenting path with respect to [math]\displaystyle{ f }[/math]. This path starts with [math]\displaystyle{ s }[/math] and ends at an arbitrary node of [math]\displaystyle{ G }[/math]. Each arc on this path is admissible and the current arc of its tail node.

Variant: One of the following actions will take place in the current iteration:

  1. An arc is appended to the current path (when going forward in the depth-first search for an augmenting path).
  2. At least one arc is saturated (when augmenting along the path up to saturation).
  3. The distance label of some node is increased (when going backward in the depth-first search for an augmenting path).

Break condition: It is [math]\displaystyle{ d(s)=n }[/math], where [math]\displaystyle{ n=|V| }[/math],

Induction basis

Abstract view:

  1. We start with some feasible flow, for example, the zero flow.
  2. Also, we start with some valid distance labeling with respect to the initial flow.
  3. Stack [math]\displaystyle{ S }[/math] is initialized so as to contain [math]\displaystyle{ s }[/math] and no other node.
  4. The current arc of each node [math]\displaystyle{ v\in V }[/math] is reset to be the very first outgoing arc of [math]\displaystyle{ v }[/math].

Implementation of step 2 in case [math]\displaystyle{ f }[/math] is initialized as the zero flow: A BFS is run on the transpose of [math]\displaystyle{ G }[/math] with start node [math]\displaystyle{ t }[/math]; the resulting distances are the [math]\displaystyle{ d }[/math]-labels.

Proof of the implementation: Clearly, it is [math]\displaystyle{ d(t)=0 }[/math], so it remains to show [math]\displaystyle{ d(v)\leq d(w)+1 }[/math] for each arc [math]\displaystyle{ a\in A }[/math]. If [math]\displaystyle{ f }[/math] is the zero flow, the arcs of the residual network [math]\displaystyle{ G_f }[/math] are exactly the arcs of [math]\displaystyle{ G }[/math]. So, the claim follows immediately from the valid distance property.

Induction step

Abstract view:

  1. Let [math]\displaystyle{ v }[/math] be the top element of [math]\displaystyle{ S }[/math], that is, the endnode of the corresponding path.
  2. If [math]\displaystyle{ v=t }[/math]:
    1. Augment the current flow along the path corresponding to [math]\displaystyle{ S }[/math] up to saturation.
    2. Remove all nodes but [math]\displaystyle{ s }[/math] from [math]\displaystyle{ S }[/math].
  3. Otherwise:
    1. While the current arc of [math]\displaystyle{ v }[/math] is not void and not admissible or points to [math]\displaystyle{ s }[/math]: Move the current arc one step forward.
    2. If the current arc of [math]\displaystyle{ v }[/math] is now void:
      1. Set [math]\displaystyle{ d(v):=\tilde{d}+1 }[/math], where [math]\displaystyle{ \tilde{d} }[/math] denotes the minimum value [math]\displaystyle{ d(w) }[/math] over all outgoing arcs [math]\displaystyle{ (v,w) }[/math] of [math]\displaystyle{ v }[/math] in the residual network.
      2. Reset the current arc of [math]\displaystyle{ v }[/math] to the beginning of the list of outgoing arcs of [math]\displaystyle{ v }[/math].
      3. Remove [math]\displaystyle{ v }[/math] from [math]\displaystyle{ S }[/math].
    3. Otherwise, that is, if the current arc is some arc [math]\displaystyle{ (v,w) }[/math]: Push [math]\displaystyle{ w }[/math] on [math]\displaystyle{ S }[/math].

Proof: The variant, points 1, 2, and 5 of the invariant, and the first sentence of point 4 of the invariant are obvious. For the second sentence of point 4, note that no admissible arc of [math]\displaystyle{ v }[/math] is skipped when the current arc is moved forward, and the current arc is reset whenever outgoing arcs may become admissible due to an increase of [math]\displaystyle{ d(v) }[/math]. Finally, point 3 of the invariant follows from the conservative increase of [math]\displaystyle{ d(v) }[/math] in step 3.2.

Correctness

First we show that the flow is maximum when the break condition applies. Due to the max-flow min-cut theorem, it suffices to show that, in this moment, there is no more flow-augmenting [math]\displaystyle{ (s,t) }[/math]-path. However, such a path would have at most [math]\displaystyle{ n-1 }[/math] arcs, and for each arc [math]\displaystyle{ (v,w) }[/math] on this path, it is [math]\displaystyle{ d(v)\leq d(w)+1 }[/math]. This implies [math]\displaystyle{ d(s)-d(t)=d(s)\leq n-1 }[/math], which contradicts the break condition.

It remains to show that the algorithm indeed terminates. This is proved by the following complexity considerations.

Complexity

Statement: The asymptotic complexity of the algorithm is in [math]\displaystyle{ \mathcal{O}(n^2m) }[/math], where [math]\displaystyle{ n=|V| }[/math] and [math]\displaystyle{ m=|A| }[/math].

Proof: First we show that no distance label [math]\displaystyle{ d(v) }[/math] may become higher than [math]\displaystyle{ n }[/math] (in particular, the total number of executions of step 3.2 over all iterations is in [math]\displaystyle{ \mathcal{O}(n^2) }[/math]).

To see that, recall that [math]\displaystyle{ d(s)\lt n }[/math] as long as the break condition is not fulfilled. Whenever the distance label [math]\displaystyle{ d(v) }[/math] of a node [math]\displaystyle{ v\in V }[/math] is increased, [math]\displaystyle{ v }[/math] is the endnode of the current path, which consists solely of admissible arcs. Due to the definition of admissible arcs, it is [math]\displaystyle{ d(v)\leq d(s) }[/math] immediately before the current iteration (equality only if [math]\displaystyle{ v=s }[/math]). Let [math]\displaystyle{ (v,w) }[/math] be an arc such that [math]\displaystyle{ \tilde{d}=d(w) }[/math], in particular, it is [math]\displaystyle{ w\neq s }[/math]. For the same reason, it is [math]\displaystyle{ d(w)\lt d(s) }[/math], which implies [math]\displaystyle{ d(v)\leq d(s) }[/math] immediately after the current iteration.

Now we know [math]\displaystyle{ d(u)\leq n }[/math] for all nodes [math]\displaystyle{ u\in V }[/math]. Next we consider an arbitrary but fixed arc [math]\displaystyle{ (v,w)\in A }[/math]. Suppose [math]\displaystyle{ (v,w) }[/math] has ben saturated at least twice during the algorithm. In both iterations, [math]\displaystyle{ (v,w) }[/math] is admissible, which means [math]\displaystyle{ d(v)\gt d(w) }[/math]. However, in the meantime, some flow must have been sent back from [math]\displaystyle{ w }[/math] to [math]\displaystyle{ v }[/math], which implies [math]\displaystyle{ d(w)\gt d(v) }[/math] in that intermediate iteration. As distance labels are non-decreasing, [math]\displaystyle{ d(v) }[/math] must have been increased between any two iterations in which [math]\displaystyle{ (v,w) }[/math] is saturated. In summary, each arc is saturated only [math]\displaystyle{ \mathcal{O}(n) }[/math] times.

In each execution of step 2.1 of the induction step, at least one arc is saturated, so the total number of executions of step 2.1+2.2 is in [math]\displaystyle{ \mathcal{O}(nm) }[/math]. The path contains at most [math]\displaystyle{ n-1 }[/math] arcs, so the total asymptotic complexity for all executions of step 2.1+2 is in [math]\displaystyle{ \mathcal{O}(n^2m) }[/math].

Finally, the sequence of outgoing arcs is passed once for each node in step 3.1 between two increases of [math]\displaystyle{ d(v) }[/math], so the total asymptotic complexity of all executions of step 3.1 over all iterations is in [math]\displaystyle{ \mathcal{O}(n\cdot m) }[/math].

Remark

This algorithm may be seen as a "lazy" variant on Edmonds-Karp. In fact, the most expensive step there is the computation of a shortest flow-augmenting [math]\displaystyle{ (s,t) }[/math]-path. This task amounts to computing the true distance from every node to [math]\displaystyle{ t }[/math]. A valid distance labeling may be seen as "lazily evaluated" true distances.