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].

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.