$\O(m \log \log n)$-time MST

個人的メモ

(補足 1)
他にも Yao 先生の $\O (m \log \log n)$ time アルゴリズムもある.
もしグラフの各頂点について隣接する辺がコストについてソートされていたなら Boruvka 法は $\O (n \log n + m)$ 時間で解ける. なぜなら各頂点についてそれに隣接する最小コストの辺はその頂点に縮約された全頂点についてそれに隣接する最小コストの辺を見れば良いからである. もちろん縮約によって自己ループとなってしまう辺についてはできたタイミングで削除しておくという状況のもとでの話でかつ適宜操作をリストの結合やリストからの削除として実現することで $1$ 回あたり $\O (1)$ の計算量で操作を行うことができる.
ここで完全なソート列ではなく次のような部分的なソート列を考える. 各頂点に隣接する辺を $k$ 個のグループ $g_1$, $g_2$, $\ldots$, $g_k$ に分け, このとき $g_i$ 内の任意の辺のコストは $g_{i+1}$ 内のどの辺のコストよりも大きくならないとする. このような分割は median of medians を用いた最悪 $\O (n)$ の k-th element アルゴリズムを用いるなどして最悪 $\O (m \log k)$ 時間でできる.
上記の $2$ つの事実を組み合わせて最初に各頂点について部分的にソートしておくとそのあとの Boruvka 法で各頂点に隣接する最小コストの辺を探索するのにかかる時間はその頂点に縮約された全頂点についてそれに隣接する辺の最小のグループのみを見ればよいので $\O (m / k)$. よって最小全域木を $\O (m \log k + (m / k) \log n + n \log n)$ 時間で求めることができる($n \log n$ の部分は $n \alpha(m, n)$ くらいにはできるかもしれないが結局頂点の縮約を管理するのに Union Find 等を使う必要があるので $\O (n)$ は無理そう). よって $k = \log n$ と定めると $m = \Omega (n \log n)$ の場合は $\O (m \log \log n)$ 時間で最小全域木を求められることが分かる.
$m = \mathrm{o}(n \log n)$ の場合にも同じ計算量を達成するためにはまず最初に $\lceil \log \log n \rceil$ 回通常の Boruvka 法を行い, 頂点数を $n / \log n$ に落としたうえで上記の修正版の Boruvka 法を動かすと良い.
この内容については CMU の Advanced Algoirthms の授業の Homework を実際に解いてみると分かる. (参考)

(補足 2)
これより速いアルゴリズムとして Fredman-Tarjan の $\O (m \log^* n)$ アルゴリズムがある. "Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms" [Fredman, Tarjan 1987]
Prim 法は Fibonacci Heap を用いることで $\O (n \log n + m)$ 時間で行えるがこれを改良する. Fibonacci Heap は要素の削除にヒープのサイズを $U$ としたとき $\O (\log U)$ のならしコストがかかってしまう. Prim 法の場合 Fibonacci Heap に入っている要素の数は既に確定している木に隣接している頂点の数に等しい. そこで保持している木に隣接する頂点の数があるしきい値を超えたら一旦そこで探索を終了してまだたどっていない新しい頂点から新たに木を構築していくみたいなことをする. そして全頂点がたどられたあと今まで構築してきた森を縮約し, サイズの小さくなったグラフの最小全域木をまた同様の操作を繰り返すことで求める. このとき森を構築し, 縮約した後のグラフについて最小全域木を求めるみたいな手順で全体の最小全域木が得られることの正当性は Boruvka 法のそれと同様にして示すことができる. 各回でしきい値を適切に設定することで $\O (m \log^* n)$ を達成できる.
ちなみに現在の最速の最小全域木アルゴリズムの計算量は $\O (m \alpha (m, n))$ で Boruvka ベースの構成 + soft heap(キー値を恣意的に変更することで情報量を落としたヒープ的なもの) で何かをするということしか知らない. "A Minimum Spanning Tree Algorithm with Inverse-Ackermann Type Complexity" [Chazelle 2000]
決定的アルゴリズムとは別に期待線形時間乱択アルゴリズム(Las Vegas) も存在する "A randomized linear-time algorithm to find minimum spanning trees" [Karger, Klein, Tarjan 1995]