Dinic: Difference between revisions
m (→Induction step: auch V wird i.A. reduziert) |
|||
| (5 intermediate revisions by one other user not shown) | |||
| Line 4: | Line 4: | ||
'''Type of algorithm :''' loop. | '''Type of algorithm :''' loop. | ||
== Abstract View == | == Abstract View == | ||
| Line 16: | Line 14: | ||
'''Variant:''' | '''Variant:''' | ||
The smallest number of arcs on a flow-augmenting <math>(s,t)</math>-path strictly increases. | The smallest number of arcs on a flow-augmenting <math>(s,t)</math>-path strictly increases. | ||
'''Break condition:''' There is no flow-augmenting <math>(s,t)</math>-path anymore. | |||
== Induction basis == | == Induction basis == | ||
| Line 28: | Line 28: | ||
'''Abstract view:''' | '''Abstract view:''' | ||
# Construct the [[Basic graph definitions#Cycles|acyclic]] [[Basic graph definitions#Subgraphs|subgraph]] <math>G'=(V,A')</math> of the residual network that contains an arc if, and only if, the arc is on at least one <math>(s,t)</math>-path with smallest number of arcs. | # Construct the [[Basic graph definitions#Cycles|acyclic]] [[Basic graph definitions#Subgraphs|subgraph]] <math>G'=(V',A')</math> of the residual network that contains an arc if, and only if, the arc is on at least one <math>(s,t)</math>-path with smallest number of arcs (and contains all nodes incident to these arcs). | ||
# Use one of the algorithms for the [[Blocking flow|blocking flow]] problem to construct a blocking flow <math>f'</math> in <math>G'</math> with respect to the residual capacities for <math>f</math>. | # Use one of the algorithms for the [[Blocking flow|blocking flow]] problem to construct a blocking flow <math>f'</math> in <math>G'</math> with respect to the residual capacities for <math>f</math>. | ||
# | # Add <math>f'</math> to <math>f</math>. | ||
'''Proof:''' Obvious. | '''Proof:''' Obvious. | ||
| Line 41: | Line 41: | ||
'''Statement:''' | '''Statement:''' | ||
The asymptotic complexity is in <math>\mathcal{O}(n\cdot T(n))</math>, where <math>T(n)</math> is the asymptotic complexity of the blocking-flow algorithm. | The asymptotic complexity is in <math>\mathcal{O}(n\cdot T(n,m))</math>, where <math>n=|V|</math>, <math>m=|A|</math>, and <math>T(n,m)</math> is the asymptotic complexity of the blocking-flow algorithm. | ||
'''Proof:''' | '''Proof:''' | ||
Evidenty, the smallest number of arcs on a flow-augmenting <math>(s,t)</math>-path cannot exceed <math>n-1</math>. Therefore, the variant implies that the algorithm terminates after <math>n-1</math> iterations. The complexity of a single iteration is dominated by the computation of a blocking flow. | Evidenty, the smallest number of arcs on a flow-augmenting <math>(s,t)</math>-path cannot exceed <math>n-1</math>. Therefore, the variant implies that the algorithm terminates after <math>n-1</math> iterations. The complexity of a single iteration is dominated by the computation of a blocking flow. | ||
Latest revision as of 10:43, 8 January 2015
General Information
Algorithmic problem: Max-flow problem (standard version)
Type of algorithm : loop.
Abstract View
Invariant: After [math]\displaystyle{ i \ge 0 }[/math] iterations:
- The flow [math]\displaystyle{ f }[/math] is feasible.
- If all upper bounds are integral, the [math]\displaystyle{ f }[/math]-values are integral as well.
Variant: The smallest number of arcs on a flow-augmenting [math]\displaystyle{ (s,t) }[/math]-path strictly increases.
Break condition: There is no flow-augmenting [math]\displaystyle{ (s,t) }[/math]-path anymore.
Induction basis
Abstract view: Initialize [math]\displaystyle{ f }[/math] as an arbitrary feasible flow, for example, the zero flow.
Proof: Nothing to show.
Induction step
Abstract view:
- Construct the acyclic subgraph [math]\displaystyle{ G'=(V',A') }[/math] of the residual network that contains an arc if, and only if, the arc is on at least one [math]\displaystyle{ (s,t) }[/math]-path with smallest number of arcs (and contains all nodes incident to these arcs).
- Use one of the algorithms for the blocking flow problem to construct a blocking flow [math]\displaystyle{ f' }[/math] in [math]\displaystyle{ G' }[/math] with respect to the residual capacities for [math]\displaystyle{ f }[/math].
- Add [math]\displaystyle{ f' }[/math] to [math]\displaystyle{ f }[/math].
Proof: Obvious.
Correctness
Feasibility of [math]\displaystyle{ f }[/math] follows immediately from the invariant. If the algorithm terminates, the break condition immediately proves maximality along with the max-flow min-cut theorem. Termination follows immediately from the following complexity considerations.
Complexity
Statement: The asymptotic complexity is in [math]\displaystyle{ \mathcal{O}(n\cdot T(n,m)) }[/math], where [math]\displaystyle{ n=|V| }[/math], [math]\displaystyle{ m=|A| }[/math], and [math]\displaystyle{ T(n,m) }[/math] is the asymptotic complexity of the blocking-flow algorithm.
Proof: Evidenty, the smallest number of arcs on a flow-augmenting [math]\displaystyle{ (s,t) }[/math]-path cannot exceed [math]\displaystyle{ n-1 }[/math]. Therefore, the variant implies that the algorithm terminates after [math]\displaystyle{ n-1 }[/math] iterations. The complexity of a single iteration is dominated by the computation of a blocking flow.