期望線性時間的 Karger-Klein-Tarjan 演算法

當確定性的演算法 (deterministic algorithms) 開始變得複雜的時候，眾人們便開始考慮隨機演算法 (randomized algorithms) 的可能性。 最小生成樹是一個很經典而且適用於前一句的標準例子：至今大家仍然不知道，確定性演算法究竟能不能做到線性時間。但隨機演算法，已經能夠做到期望線性時間了！

將隨機方法導入圖論演算法這個領域並進行分析的，任職於 MIT 的 David Karger 教授應該是第一人了吧。今天我們將介紹 Karger, Klein 以及 Tarjan 等人利用一個絕妙觀察設計出來的期望線性時間演算法¹。

『驗證最小生成樹演算法』的應用

還記得我們前一篇提到的驗證最小生成樹的 \(O(m+n)\) 線性時間演算法嗎？ 給定一個圖 \(G=(V, E)\) 以及圖上一棵生成樹 \(F\)，該演算法除了能夠回答『\(F\) 是否為 \(G\) 的最小生成樹』的是非題以外， 其實能做到更多的事情：它能夠在線性時間找出所有用來否決該陳述的所有邊。

『否決陳述的邊』是什麼意思呢？其實就是能夠拿出來當作證據說 \(F\) 並非圖 \(G\) 最小生成樹的一條邊 \(e=(u, v)\)： 這條邊的兩個端點 \(u\)、\(v\) 在 \(F\) 中對應路徑上權重最大的邊，其權重竟然比 \(e\) 的權重還大。而這個證據 \(e\) 就能夠用來說明 \(F\) 上面存在一條非安全邊，從而否決 \(F\) 為 \(G\) 的最小生成樹的陳述。 我們不妨稱否決陳述的邊 \(e\) 為一條 \(F\)-輕邊 (\(F\)-light edge)；反之若 \(e\) 並非否決陳述的邊，我們便稱 \(e\) 為一條 \(F\)-重邊 (\(F\)-heavy edge)。

而驗證最小生成樹的演算法，無論是 Hagerup、King、或是 Dixon-Rauch-Tarjan 演算法，都能夠在線性時間內判斷給定的邊孰輕孰重、並將之分成兩堆。也就是說，我們可以把驗證最小生成樹的演算法當作一個黑盒子，把要分堆的邊 \(E_0 := E\setminus F\) 丟進去黑盒子裡。每跑一次，就能將 \(E'\) 的邊分成兩堆 \(F^{(E_0)}_{\text{light}}\) 以及 \(F^{(E_0)}_{\text{heavy}}\)。其中 \(F^{(E_0)}_{\text{light}}\) 包含了所有的『否決陳述的邊』，也就是 \(F\)-輕邊；而 \(F^{(E_0)}_{\text{heavy}}\) 則包含了所有的 \(F\)-重邊。不難推敲，所有 \(F^{(E_0)}_{\text{heavy}}\) 內的邊都可以被丟掉：

性質 MST.19

給定圖 \(G\) 以及圖上任意一棵生成樹 \(F\)。那麼圖 \(G\) 的最小生成樹不包含任何 \(F^{(E_0)}_{\text{heavy}}\) 內的邊。

如果 \(F_{\text{heavy}}\) 裡面的邊超多，多到比方說 \(\ge 0.1(m-n)\) 這麼多條。那麼選定了這個 \(F\) 我們就能在線性時間，把圖上的邊減少為 \(0.9\) 倍。若我們重複這樣『選生成樹、呼叫驗證最小生成樹的黑盒子、把重邊丟光光』的操作流程，並且每一次都能夠讓多餘的邊數減少一個常數倍的話，我們就能得到一個線性時間的演算法了！

於是現在的問題變成了：這麼好的 \(F\) 要去哪裡找？

Karger、Klein 與 Tarjan 等人想到了：那為什麼不借助隨機抽樣的力量，先隨機抽樣一個 \(G\) 的子圖，然後算個大概，找出該子圖的最小生成樹 \(F\)，然後再用 \(F\) 篩選出剩下的 \(F_{\text{light}}\) 邊。接著將 \(F\cup F_{\text{light}}\) 丟入遞迴。

Karger-Klein-Tarjan 的絕妙觀察

參考資料