Blocking flow by Dinic: Difference between revisions

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


'''Break condition:'''
'''Break condition:'''
There is no more [[Basic flow definitions#Flow-augmenting path|flow-augmenting]] ordinary <math>(s,t)</math>-path in <math>G</math> (that is, all arcs on the path are forward arcs).
There is no more [[Basic flow definitions#Flow-augmenting paths and saturated arcs|flow-augmenting]] [[Basic graph definitions#Paths|ordinary <math>(s,t)</math>-path]] in <math>G</math>.


== Induction basis ==
== Induction basis ==
Line 30: Line 30:


'''Abstract view:'''
'''Abstract view:'''
# Run a [[Depth-first search|DFS]] from <math>s</math> that may [[Graph traversal#Remarks|terminate early]], namely if <math>t</math> is seen.
# Run a [[Depth-first search|DFS]] from <math>s</math> with two modifications: (1) The search may [[Graph traversal#Remarks|terminate early]], namely when <math>t</math> is seen; (2) whenever the search goes backwards from some node, this node and all of its incident arcs are removed from <math>G</math>.
# If <math>t</math> is ''not'' seen, the break condition applies, and the algorithm is terminated.
# If <math>t</math> is ''not'' seen, the break condition applies, and the algorithm is terminated.
# Otherwise:
# Otherwise:
## Let <math>p</math> be the <math>(s,t)</math>-path found in step 1.
## Let <math>p</math> be the ordinary <math>(s,t)</math>-path found in step 1.
## Let <math>\Delta</math> be the minimum of the values <math>u(a)</math> of all arcs <math>a</math> on <math>p</math>.
## Let <math>\Delta</math> be the minimum of the values <math>u(a)</math> of all arcs <math>a</math> on <math>p</math>.
## For each arc <math>a</math> on <math>p</math>:
## For each arc <math>a</math> on <math>p</math>:
### Increase <math>f(a)</math> by <math>\Delta</math> and decrease <math>u(a)</math> by <math>\Delta</math>.
### Increase <math>f(a)</math> by <math>\Delta</math> and decrease <math>u(a)</math> by <math>\Delta</math>.
### If <math>u(a)=0</math>, remove <math>a</math> from <math>G</math>.
### If <math>u(a)=0</math>, remove <math>a</math> from <math>G</math>.
### If the tail of <math>a</math> has no outgoing arcs anymore, it is removed as well.


'''Proof:'''
'''Proof:'''
Feasibility of the flow follows immediately from the fact that the flow is increased by a constant amount over an <math>(s,t)</math>, and from the specific choice of <math>\Delta</math> (see the [[Ford-Fulkerson#Induction step|proof]] of the induction step of Ford-Fulkerson for details). Also, the specific choice of <matH>\Delta</math> ensures that at least one arc is saturated in step 3.3.1 and, hence, removed in step 3.3.2.
Feasibility of the flow follows immediately from the fact that the flow is increased by a constant amount over an <math>(s,t)</math>-path, and from the specific choice of <math>\Delta</math>. Also, the specific choice of <matH>\Delta</math> ensures that at least one arc is saturated in step 3.3.1 and, hence, removed in step 3.3.2.
 
== Correctness ==
 
The variant implies termination. Since the graph is acyclic and the arcs are only considered in forward direction by the DFS, a node <math>v\in V</math> is indeed removed only if there is no flow-augmenting ordinary <math>(v,t)</math>-path. Hence, the set of flow-augmenting ordinary <math>(s,t)</math>-paths is not reduced by the node removals. So, the break condition, though applied to the reduced graph, also implies for the original graph that the flow is blocking on termination.


== Complexity ==
== Complexity ==


'''Statement:'''
'''Statement:'''
The asympütotic complexity is in <math>\mathcal{O}(n\cdot m)</math>, where <math>n=|V|</math> and <math>m=|A|</math>,
The asymptotic complexity is in <math>\mathcal{O}(n\cdot m)</math>, where <math>n=|V|</math> and <math>m=|A|</math>,
 
'''Proof:'''
Due to the variant, the number of iterations is linear in the number of arcs. The second modification of  the search in step 1 ensures that the total number of backward steps over all iterations of the main loop is linear in the number of nodes. The number of forward steps within one iteration is linear in the number of nodes because every node is removed before it can be seen a second time.

Latest revision as of 08:37, 7 December 2015

General information

Algorithmic problem: Blocking flow.

Type of algorithm: loop.

Abstract view

Invariant: The current flow is feasible.

Variant: The number of arcs decreases.

Break condition: There is no more flow-augmenting ordinary [math]\displaystyle{ (s,t) }[/math]-path in [math]\displaystyle{ G }[/math].

Induction basis

Abstract view: Initialize [math]\displaystyle{ f }[/math] to be a feasible flow, for example, the zero flow.

Implementation: Obvious.

Proof: Obvious.

Induction step

Abstract view:

  1. Run a DFS from [math]\displaystyle{ s }[/math] with two modifications: (1) The search may terminate early, namely when [math]\displaystyle{ t }[/math] is seen; (2) whenever the search goes backwards from some node, this node and all of its incident arcs are removed from [math]\displaystyle{ G }[/math].
  2. If [math]\displaystyle{ t }[/math] is not seen, the break condition applies, and the algorithm is terminated.
  3. Otherwise:
    1. Let [math]\displaystyle{ p }[/math] be the ordinary [math]\displaystyle{ (s,t) }[/math]-path found in step 1.
    2. Let [math]\displaystyle{ \Delta }[/math] be the minimum of the values [math]\displaystyle{ u(a) }[/math] of all arcs [math]\displaystyle{ a }[/math] on [math]\displaystyle{ p }[/math].
    3. For each arc [math]\displaystyle{ a }[/math] on [math]\displaystyle{ p }[/math]:
      1. Increase [math]\displaystyle{ f(a) }[/math] by [math]\displaystyle{ \Delta }[/math] and decrease [math]\displaystyle{ u(a) }[/math] by [math]\displaystyle{ \Delta }[/math].
      2. If [math]\displaystyle{ u(a)=0 }[/math], remove [math]\displaystyle{ a }[/math] from [math]\displaystyle{ G }[/math].

Proof: Feasibility of the flow follows immediately from the fact that the flow is increased by a constant amount over an [math]\displaystyle{ (s,t) }[/math]-path, and from the specific choice of [math]\displaystyle{ \Delta }[/math]. Also, the specific choice of [math]\displaystyle{ \Delta }[/math] ensures that at least one arc is saturated in step 3.3.1 and, hence, removed in step 3.3.2.

Correctness

The variant implies termination. Since the graph is acyclic and the arcs are only considered in forward direction by the DFS, a node [math]\displaystyle{ v\in V }[/math] is indeed removed only if there is no flow-augmenting ordinary [math]\displaystyle{ (v,t) }[/math]-path. Hence, the set of flow-augmenting ordinary [math]\displaystyle{ (s,t) }[/math]-paths is not reduced by the node removals. So, the break condition, though applied to the reduced graph, also implies for the original graph that the flow is blocking on termination.

Complexity

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

Proof: Due to the variant, the number of iterations is linear in the number of arcs. The second modification of the search in step 1 ensures that the total number of backward steps over all iterations of the main loop is linear in the number of nodes. The number of forward steps within one iteration is linear in the number of nodes because every node is removed before it can be seen a second time.