Frederickson's MST Algorithm

Purpose: Greg Frederickson’s work on spanning trees covers two related results:

1. Dynamic MST maintenance in $O(\sqrt{m})$ per edge update, via topology trees and the ambivalent data structure;
2. Topology trees — a general tree-clustering structure for dynamic tree problems.

The closely related Fredman-Tarjan algorithm (often confused with this one) computes a static MST in $O(m{\log }^{\ast }n)$.

---

Topology trees

Partition a bounded-degree tree into clusters of $O(1)$ vertices, then recursively cluster the cluster graph, building a balanced hierarchy of $O(\log n)$ levels. Each level shrinks the tree by a constant factor.

This gives:

• $O(\log n)$ path and subtree aggregate queries;
• $O(\log n)$ link and cut;
• support for non-local information (like “the minimum edge crossing a cut”), which is what dynamic MST needs and what plain link-cut trees handle less naturally.

Dynamic MST

Maintain a spanning forest under edge insertion and deletion:

• Insert $(u,v,w)$: if $u,v$ are in different components, add it. Otherwise find the maximum-weight edge on the tree path $u\to v$; if it exceeds $w$, swap. This is a path-max query — $O(\log n)$ with topology trees.
• Delete a tree edge: the hard case. The tree splits into two components and you must find the minimum replacement edge crossing the cut. Frederickson’s ambivalent data structure partitions the edges so that this search takes $O(\sqrt{m})$.

$\text{Update: }O(\sqrt{m}).$

With the sparsification technique of Eppstein, Galil, Italiano and Nissenzweig this improves to $O(\sqrt{n})$.

Complexity landscape for dynamic connectivity / MST

Problem	Best known	Technique
Incremental connectivity	$O(\alpha )$ amortized	DSU
Decremental connectivity (trees)	$O(1)$ amortized	Euler tour + tricks
Fully dynamic connectivity	$O({\log }^{2}n)$ amortized	HDT
Fully dynamic MST	$O({\log }^{4}n)$ amortized	HDT extension
Frederickson (original)	$O(\sqrt{m})$ worst case	topology trees
Offline dynamic connectivity	$O({\log }^{2}n)$	segment tree on time + rollback DSU

What to write in a contest

Offline dynamic connectivity: put each edge’s lifetime as an interval on a segment tree over the time axis, DFS the segment tree, and use a rollback DSU. About 60 lines, $O(m\log m\alpha )$, and it handles the overwhelming majority of dynamic-graph problems that appear in contests. See Dynamic Connectivity.

Fredman-Tarjan (the static algorithm)

Runs Prim with a Fibonacci heap but stops each growth phase once the heap exceeds a size threshold $k$, contracts what it has, and restarts with a larger threshold. Each pass raises the threshold from $k$ to $2^{2m/k}$, so the number of passes is $O({\log }^{\ast }n)$, giving $O(m{\log }^{\ast }n)$ total.

Variants / Use Cases

• Link-Cut Trees — the other dynamic tree structure; simpler to implement, handles path aggregates
• Dynamic Connectivity — the topic page
• Chazelle — the deterministic $O(m\alpha )$ static MST
• Minimum Spanning Tree — the topic page