Ahuja-Orlin: Difference between revisions
| (47 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
== General Information == | == General Information == | ||
'''Algorithmic problem:''' [[Max-Flow Problems]] | '''Algorithmic problem:''' [[Max-Flow Problems#Standard version|Max-flow problems (standard version)]] | ||
'''Type of algorithm:''' loop | '''Type of algorithm:''' loop | ||
== 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 | # 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 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 | # 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:''' | ||
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:''' <math>d(s) | '''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|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: | ||
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>. | |||
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: | ## 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 | 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 == | |||
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 considerations. | |||
== Complexity == | == Complexity == | ||
'''Statement:''' | |||
The asymptotic complexity of the algorithm is in <math>\mathcal{O}(n^2m)</math>, where <math>n=|V|</math> and <math>m=|A|</math>. | |||
'''Proof:''' | |||
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> | 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, at least one arc is saturated, so the total number of executions of step 2.1 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 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 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:
- A nonnegative integral value [math]\displaystyle{ d(v) }[/math] for each node [math]\displaystyle{ v\in V }[/math].
- 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].
- A stack [math]\displaystyle{ S }[/math] of nodes.
Invariant: After [math]\displaystyle{ i \ge 0 }[/math] iterations:
- The flow [math]\displaystyle{ f }[/math] is a feasible flow.
- If all upper bounds are integral, [math]\displaystyle{ f }[/math] is integral as well.
- The values [math]\displaystyle{ d(\cdot) }[/math] are a valid distance labeling with respect to [math]\displaystyle{ f }[/math].
- 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].
- 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:
- An arc is appended to the current path (when going forward in the depth-first search for an augmenting path).
- At least one arc is saturated (when augmenting along the path up to saturation).
- 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:
- We start with some feasible flow, for example, the zero flow.
- Also, we start with some valid distance labeling with respect to the initial flow.
- Stack [math]\displaystyle{ S }[/math] is initialized so as to contain [math]\displaystyle{ s }[/math] and no other node.
- 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:
- Let [math]\displaystyle{ v }[/math] be the top element of [math]\displaystyle{ S }[/math], that is, the endnode of the corresponding path.
- If [math]\displaystyle{ v=t }[/math]:
- Augment the current flow along the path corresponding to [math]\displaystyle{ S }[/math] up to saturation.
- Remove all nodes but [math]\displaystyle{ s }[/math] from [math]\displaystyle{ S }[/math].
- Otherwise:
- 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.
- If the current arc of [math]\displaystyle{ v }[/math] is now void:
- 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.
- Reset the current arc of [math]\displaystyle{ v }[/math] to the beginning of the list of outgoing arcs of [math]\displaystyle{ v }[/math].
- Remove [math]\displaystyle{ v }[/math] from [math]\displaystyle{ S }[/math].
- 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.