期望線性時間的 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 的絕妙觀察

參考資料