Dinic: Difference between revisions

From Algowiki
Jump to navigation Jump to search
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 (and all nodes incident to these 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>.
# For all arcs <math>a\in A</math>, add <math>f'</math> to <math>f</math>.
# For all arcs <math>a\in A</math>, add <math>f'</math> to <math>f</math>.

Revision as of 10:30, 10 November 2014

General Information

Algorithmic problem: Max-flow problem (standard version)

Type of algorithm : loop.

Abstract View

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

  1. The flow [math]\displaystyle{ f }[/math] is feasible.
  2. 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:

  1. 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).
  2. 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].
  3. For all arcs [math]\displaystyle{ a\in A }[/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.