Pettie-Ramachandran MST Algorithm

Purpose: A minimum spanning tree algorithm that is provably optimal — it runs in time $O({\mathcal{T}}^{\ast }(m,n))$, where ${\mathcal{T}}^{\ast }$ is the unknown decision-tree complexity of the MST problem. Pettie and Ramachandran (2002).

The strange claim

This is one of the most unusual results in algorithms: the algorithm’s running time is optimal, yet nobody knows what that running time is. We know:

$\Omega (m)\le {\mathcal{T}}^{\ast }(m,n)\le O(m\alpha (m,n)),$

but the exact function is open. The algorithm is optimal relative to itself being the best possible.

How it works

1. Partition the graph into small subgraphs of size $r=O(\log \log \log n)$ vertices, using Borůvka steps and a soft-heap-based procedure borrowed from Chazelle.
2. For each tiny subgraph, look up a precomputed optimal decision tree — the theoretically best comparison sequence for a graph of that size. Because $r$ is so small, all such decision trees can be found by brute force in $o(n)$ total time.
3. Contract the results and recurse on the much smaller graph.

Step 2 is why the algorithm is optimal: on the small pieces it is the optimal algorithm by construction, and the surrounding machinery contributes only linear overhead.

Complexity

• Time: $\Theta ({\mathcal{T}}^{\ast }(m,n))$, which is between $\Omega (m)$ and $O(m\alpha (m,n))$
• Space: $O(m)$

Why this is worth knowing

It is a clean example of the “algorithm by table lookup on tiny subproblems” technique — the same four-Russians idea that powers Farach-Colton-Bender RMQ, $O(n^3/\log n)$ boolean matrix multiplication, and precomputed-block bitset DP. Once a subproblem is small enough that every possible instance can be enumerated, you get optimality for free on that scale.

It also sharpens what the open problem actually is: not “find a faster MST algorithm” — we already have an optimal one — but “analyse the one we have”.

The MST story so far

Year	Result	Time
1926	Borůvka	$O(m\log n)$
1956/57	Kruskal, Prim	$O(m\log n)$
1975	Yao	$O(m\log \log n)$
1984	Fredman-Tarjan	$O(m{\log }^{\ast }n)$
1986	Gabow et al.	$O(m\log {\log }^{\ast }n)$
1995	Karger-Klein-Tarjan	$O(m)$ randomized
2000	Chazelle	$O(m\alpha (m,n))$ deterministic
2002	Pettie-Ramachandran	optimal, value unknown

Still open: a deterministic $O(m)$ algorithm, and the value of ${\mathcal{T}}^{\ast }$.

Variants / Use Cases

• Minimum Spanning Tree — what you should actually implement
• Chazelle — soft heaps, the tool this builds on
• Four Russians — the small-subproblem-table technique in a form you might actually use