Gabow-Tarjan Algorithm

Purpose: Solve the assignment problem (minimum-cost perfect matching in a bipartite graph) in $O(\sqrt{n}m\log (nC))$ using cost scaling — faster than the $O(n^3)$ Hungarian algorithm when costs are moderate.

Gabow and Tarjan also produced a well-known linear-time special case of union-find, described below.

---

Assignment by cost scaling

Algorithm

1. Scale the costs: work with $\lceil \log (nC)\rceil$ phases, in phase $k$ using $c_k(e)=\lceil c(e)/2^{\text{phases}-k}\rceil$.
2. Maintain $\epsilon$-optimality via dual prices $y(v)$: every edge satisfies $c(u,v)-y(u)-y(v)\ge -\epsilon$.
3. In each phase, halve $\epsilon$ and repair the matching using Hopcroft-Karp-style phases of vertex-disjoint augmenting paths, which is where the $\sqrt{n}$ comes from.
4. When $\epsilon <1/n$, integrality forces exact optimality.

Complexity

$O(\sqrt{n}m\log (nC))$

versus:

Algorithm	Time
Brute force over permutations	$O(n!)$
Bitmask DP	$O(2^{n}n)$ — best for $n\le 20$
Hungarian	$O(n^3)$ — the contest default
MCMF with potentials	$O(n\cdot m\log n)$
Gabow-Tarjan	$O(\sqrt{n}m\log (nC))$

What to write

Hungarian, $O(n^3)$. For $n\le 500$ it runs in well under a second, and the implementation is ~40 lines. Use bitmask DP instead when $n\le 20$ and the cost structure is irregular.

---

Gabow-Tarjan union-find

A separate famous result: union-find in $O(m+n)$ time, not $O(m\alpha (n))$, for the special case where the sequence of unions is known to follow a fixed tree structure given in advance.

The trick is a two-level micro/macro decomposition: split the tree into micro-trees of $O(\log n)$ vertices, solve each by table lookup (four Russians), and run ordinary union-find on the $O(n/\log n)$ macro nodes. The $\alpha$ factor applies only to the tiny macro instance, where it is absorbed.

This is exactly what makes Tarjan’s offline LCA genuinely linear rather than $O(n\alpha (n))$, and it underlies linear-time algorithms for verifying minimum spanning trees.

Variants / Use Cases

• Hungarian algorithm — the practical assignment solver
• Gabow-Edmonds scaling — the general scaling framework
• DSU — the structure the linear-time result refines
• Assignment Problem — the problem page