# Dinic

## Contents

## General Information

**Algorithmic problem:** Max-flow problem (standard version)

**Type of algorithm :** loop.

## Abstract View

**Invariant:**
After iterations:

- The flow is feasible.
- If all upper bounds are integral, the -values are integral as well.

**Variant:**
The smallest number of arcs on a flow-augmenting -path strictly increases.

**Break condition:** There is no flow-augmenting -path anymore.

## Induction basis

**Abstract view:**
Initialize as an arbitrary feasible flow, for example, the zero flow.

**Proof:**
Nothing to show.

## Induction step

**Abstract view:**

- Construct the acyclic subgraph of the residual network that contains an arc if, and only if, the arc is on at least one -path with smallest number of arcs (and contains all nodes incident to these arcs).
- Use one of the algorithms for the blocking flow problem to construct a blocking flow in with respect to the residual capacities for .
- Add to .

**Proof:** Obvious.

## Correctness

Feasibility of 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 , where , , and is the asymptotic complexity of the blocking-flow algorithm.

**Proof:**
Evidenty, the smallest number of arcs on a flow-augmenting -path cannot exceed . Therefore, the variant implies that the algorithm terminates after iterations. The complexity of a single iteration is dominated by the computation of a blocking flow.