Ahuja-Orlin: Difference between revisions

From Algowiki
Jump to navigation Jump to search
 
(14 intermediate revisions by the same user not shown)
Line 14: Line 14:
'''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.
# The values <math>d(\cdot)</math> are a [[Basic flow definitions#Valid distance labeling|valid distance labeling]] 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>.
Line 22: Line 22:
'''Variant:'''
'''Variant:'''
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 32: 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|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''' of step 2 in case <math>f</math> is initialized as the zero flow:
'''Implementation''' of step 2 in case <math>f</math> is initialized as the zero flow:
A [[Breadth-first search|BFS]] is run on the [[Basic graph definitions#Transpose|transpose]] of <math>G</math> with start node <math>t</math> and unit arc lengths; the resulting distances are the <math>d</math>-labels.
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.


'''Proof:'''
'''Proof of the implementation:'''
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>.
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 [[Basic graph definitions#Path lengths and distances|valid distance property]].
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 48: 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>:
## [[Basic flow definitions#Augmenting along a path|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:
Line 55: Line 55:
### 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.
### 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>.
### 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>.


Line 64: Line 65:
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 ==

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.