Goldberg-Tarjan Scaling Algorithm

Purpose: Two related results from Goldberg and Tarjan:

1. Max flow in $O(nm\log (n^2/m))$ — push-relabel accelerated with dynamic trees;
2. Min-cost flow by cost scaling in $O(nm\log n\log (nC))$, where $C$ is the largest cost — the standard fast min-cost-flow algorithm.

---

Max flow with dynamic trees

Plain push-relabel spends $O(n^{2}m)$ on non-saturating pushes, because each one moves flow along a single edge. Dynamic trees let you maintain the current “path of pushes” as a tree and push along an entire path in $O(\log n)$:

• link, cut, and “minimum residual capacity on the path to the root” are all $O(\log n)$ amortized in a link-cut tree;
• a non-saturating push becomes a path operation instead of $O(1)$ edge operations, but there are far fewer of them.

$O(n^{2}m)⟶O\left(nm\log \frac{n^2}{m}\right).$

---

Min-cost flow by cost scaling

The min-cost-flow analogue of capacity scaling, built on $\epsilon$-optimality.

$\epsilon$-optimal flow

With potentials $\pi$, the reduced cost of an arc is $c^{\pi }(u,v)=c(u,v)+\pi (u)-\pi (v)$. A flow is $\epsilon$-optimal if every residual arc has $c^{\pi }\ge -\epsilon$. At $\epsilon =0$ this is exact optimality (complementary slackness).

Algorithm

1. Start with $\epsilon =C$ (the maximum arc cost) and the zero flow, which is trivially $C$-optimal.
2. Refine: given an $\epsilon$-optimal flow, produce an $(\epsilon /2)$-optimal one. This is done with a push-relabel loop where “admissible” means $c^{\pi }<0$ rather than a height comparison.
3. Halve $\epsilon$ and repeat.
4. When $\epsilon <1/n$, the flow is exactly optimal — because reduced costs are integers, and an $\epsilon <1/n$ violation summed around any cycle cannot reach 1.

Complexity

• $O(\log (nC))$ scaling phases
• Each refine is $O(nm\log n)$ with dynamic trees, or $O(n^{2}m)$ without
• Total: $O(nm\log n\log (nC))$

Min-cost flow: which algorithm?

Algorithm	Time	Notes
Cycle cancelling	$O(n{m}^{2}CU)$	simple, pseudo-polynomial
Min-mean cycle cancelling	$O(n^2{m}^3\log n)$	strongly polynomial (Karp)
SSP with potentials (Johnson reweighting + Dijkstra)	$O(F\cdot m\log n)$	write this in contests
Capacity scaling SSP	$O(m^2\log n\log U)$
Goldberg-Tarjan cost scaling	$O(nm\log n\log (nC))$	the fast general-purpose choice
Network simplex	exponential worst case	often fastest in practice

In a contest

Successive shortest paths with Johnson potentials: run Bellman-Ford once for the initial potentials (needed if there are negative costs), then repeatedly Dijkstra on reduced costs, updating potentials each round. About 80 lines and fast enough whenever the total flow $F$ is small — which it usually is, since flow value is typically $O(n)$ in matching-style problems.

Variants / Use Cases

• Minimum Cost Flow — the topic page with modelling patterns
• Push-relabel — the base framework
• Hungarian algorithm — the assignment special case, $O(n^3)$
• Link-cut trees — the structure that removes the extra factor