Blocking flow by Dinic

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] (that is, all arcs on the path are forward arcs).

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] that may terminate early, namely if [math]\displaystyle{ t }[/math] is seen.
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 [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].
      3. If the tail of [math]\displaystyle{ a }[/math] has no outgoing arcs anymore, it is removed as well.

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] (see the proof of the induction step of Ford-Fulkerson for details). 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.

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. Since nodes without outgoing arc are removed, the seach reaches