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, a path with no backward 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] 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 [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] (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.

Correctness

The break condition implies that the flow is blocking at the end.

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 ensures that the total number of backward steps over all iterations of the main loop is linear in the number of nodes. The numbr of forward steps within one iteration is linear in the number of nodes.