Chazelle's MST Algorithm

Purpose: Compute a minimum spanning tree in $O(m\alpha (m,n))$ time, where $\alpha$ is the inverse Ackermann function — the fastest known deterministic comparison-based MST algorithm (Chazelle, 2000).

The Idea: soft heaps

The bottleneck in Borůvka-style MST algorithms is finding minimum outgoing edges. Chazelle’s algorithm uses a soft heap (also Chazelle’s invention), a priority queue that is allowed to lie:

A soft heap supports insert, meld and extract-min in $O(1)$ amortized time, at the price of “corrupting” at most an $\epsilon$ fraction of the inserted keys — their stored values may be increased.

Trading exact correctness for constant-time operations breaks the $\Omega (n\log n)$ comparison barrier that a truthful heap imposes.

Algorithm outline

1. Run Borůvka phases to contract the graph, reducing the vertex count geometrically.
2. Build a hierarchy of contractible subgraphs guided by a $t$-ary tree whose depth is chosen so the corruption stays controlled.
3. Use soft heaps to find approximate minimum edges quickly. Corrupted edges are set aside into a “bad” set.
4. Recursively clean up the bad edges, whose number is bounded by the corruption parameter.

The interplay of the hierarchy depth and the corruption rate is what produces the inverse-Ackermann bound.

Complexity

• Time: $O(m\alpha (m,n))$ deterministic
• Space: $O(m)$

The MST complexity landscape

Algorithm	Time	Notes
Kruskal	$O(m\log m)$	sort + DSU; write this
Prim + binary heap	$O(m\log n)$	good for dense graphs with an array
Prim + Fibonacci heap	$O(m+n\log n)$	theoretical improvement
Borůvka	$O(m\log n)$	parallelisable, basis of the fast ones
Fredman-Tarjan	$O(m{\log }^{\ast }n)$	packet-based Prim/Borůvka hybrid
Gabow-Galil-Spencer-Tarjan	$O(m\log {\log }^{\ast }n)$
Chazelle	$O(m\alpha (m,n))$	best deterministic known
Karger-Klein-Tarjan	$O(m)$ expected	randomized, linear
Pettie-Ramachandran	optimal	provably optimal, constant unknown

The open problem

Whether a deterministic linear-time MST algorithm exists is still open. We have a randomized linear algorithm (Karger-Klein-Tarjan), a provably optimal algorithm whose running time nobody can name (Pettie-Ramachandran), and Chazelle’s $\alpha$ bound — but not a deterministic $O(m)$ one.

Soft heaps elsewhere

The soft heap is independently useful. It gives a clean $O(n)$ selection algorithm (an alternative to median-of-medians), and appears in dynamic graph algorithms wherever “approximately correct is good enough”.

Variants / Use Cases

• Minimum Spanning Tree — the topic page and what to write in practice
• Kruskal — the contest answer, always
• MST verification — checking a given tree is minimum is solvable in deterministic $O(m)$ (King’s algorithm), which is part of why linear construction feels within reach
• Complexity theory — $\alpha (m,n)$ and where inverse Ackermann shows up