Karzanov Algorithm

Purpose: Alexander Karzanov’s 1974 $O(n^3)$ maximum flow algorithm — the first to introduce the preflow, the concept that push-relabel would later build its entire framework on.

The key concept: preflow

A flow requires conservation at every internal vertex (inflow = outflow). A preflow relaxes this to
$\text{inflow}(v)\ge \text{outflow}(v),$
allowing vertices to hold excess. This is a huge liberation: you can push flow forward aggressively without checking whether it can all get through, and clean up afterwards.

Algorithm

Within each level graph (as in Dinic):

1. Saturate every edge out of $s$, creating a preflow with excess at $s$‘s neighbours.
2. Forward phase. Process vertices by increasing level. At each vertex with excess, push as much as possible along outgoing level-graph edges.
3. Backward phase. Some excess cannot reach $t$ (the downstream capacity ran out). Process vertices by decreasing level, returning excess back toward $s$ along the edges it arrived on.
4. Repeat until no excess remains anywhere. The preflow is now a genuine blocking flow.
5. Rebuild the level graph and repeat; $O(n)$ phases suffice.

Complexity

• Blocking flow: $O(n^2)$
• Total: $O(n^3)$
• Space: $O(n^2)$ with an adjacency matrix

Historical importance

The preflow idea is Karzanov’s lasting contribution. Goldberg and Tarjan’s push-relabel algorithm (1986) took the preflow and discarded the level graph entirely, replacing it with a height function and purely local push/relabel operations. That change turned a phase-structured algorithm into a fully local one, which is what made it parallelisable and, in practice, the fastest max-flow family.

The lineage of $O(n^3)$ flow

Algorithm	Year	Mechanism
Karzanov	1974	preflow + forward/backward phases
MPM	1978	vertex potentials, min-potential pushes
Goldberg-Tarjan push-relabel	1986	preflow + height function, fully local

All three achieve $O(n^3)$; push-relabel with the highest-label rule and the gap heuristic is the one that survives in practice.

Variants / Use Cases

• Push-relabel — the descendant you should implement
• Dinic — the level-graph framework
• Maximum Flow — the topic page
• Karzanov’s other results — he also proved the $O(m\sqrt{n})$ bound for unit-capacity Dinic and worked extensively on multicommodity flow