Gabow-Edmonds Scaling Algorithm

Purpose: Harold Gabow’s bit scaling technique applied to weighted matching and shortest paths, building on Edmonds’ matching theory. The general recipe turns a weighted problem into $O(\log C)$ nearly-unweighted ones.

The bit-scaling recipe

Given weights $w(e)$ with $C=\max w$:

1. Let $w_k(e)=\lfloor w(e)/2^{\lceil \log C\rceil -k}\rfloor$ — the top $k$ bits of each weight.
2. Solve the problem for $w_1$ (weights in $\{0,1\}$ — nearly unweighted, hence cheap).
3. Given an optimal solution for $w_k$, note that $w_{k+1}(e)\in \{2w_k(e),2w_k(e)+1\}$. So doubling the previous solution gives something within $O(n)$ of optimal for $w_{k+1}$, and $O(n)$ augmentations repair it.
4. After $\lceil \log C\rceil$ rounds, $w_k=w$ and the solution is exact.

The scaling factor $\log C$ replaces a factor of $C$ — turning pseudo-polynomial into weakly polynomial.

Applied to weighted matching

Gabow’s scaling algorithm for maximum weight perfect matching in general graphs runs in

$O\left(n^{3/4}m\log C\right)$

versus $O(n^3)$ or $O(nm\log n)$ for the classical Blossom-based weighted algorithm. For bipartite graphs the corresponding bound is $O(\sqrt{n}m\log (nC))$, improving on the $O(n^3)$ Hungarian algorithm.

Applied to shortest paths

Goldberg’s scaling algorithm solves single-source shortest paths with negative edge weights in

$O(m\sqrt{n}\log C),$

beating Bellman-Ford’s $O(nm)$ when $C$ is moderate. (In 2022 Bernstein-Nanongkai-Wulff-Nilsen gave a near-linear $\tilde{O}(m{\log }^8(n)\log C)$ algorithm for the same problem.)

Why scaling works so generally

Two properties make a problem scalable:

1. Doubling preserves near-optimality. An optimal solution for the top $k$ bits, scaled by 2, is close to optimal for the top $k+1$ bits.
2. Repair is cheap. The gap can be closed with a bounded number of augmenting-path or local-improvement steps.

Almost every combinatorial optimisation problem with integer weights satisfies both, which is why scaling appears in max flow (Ahuja-Orlin), min-cost flow (Goldberg-Tarjan), matching, shortest paths, and assignment.

In practice

Scaling algorithms are rarely written for contests: the constants are large, the code is long, and $C$ is usually small enough that the simple algorithm fits in the time limit. The idea is still worth carrying, because “solve the high bits first, then refine” occasionally cracks a problem that resists direct attack — for instance building an answer bit by bit from the most significant bit down, checking feasibility at each step.

Variants / Use Cases

• Blossom algorithm — the matching theory underneath
• Hungarian algorithm — the bipartite weighted matching classic
• Gabow-Tarjan — scaling applied to the assignment problem
• Bipartite Matching and General Matching — the topic pages