separator | Finite Playground

在開始之前, 仍然要先提到這個禮拜大家持續關注的 $P \neq NP$ 的證明: 在 Lipton 的網誌最新文章(以及留言)中, 似乎準確的指出了該證明的問題; 若是接下來 Vinay Deolalikar 沒有在下一個版本的論文中給出對應的回答的話, 我想這個宣稱就要岌岌可危了. 不過同時我也為著全球頂尖的數學家和資訊科學家能在網路上有這樣大規模, 有組織架構的討論以及想法的交流感到興奮, 這正是在我們華人圈子所缺乏的. 也許這樣的想法很天真, 但是如果能少一些在意自己對論文的貢獻, 也許反而能使眾人更快明瞭以及學習新的知識, 知識的拓展也才能更加快速. 但也許要等到有這樣的身分跟地位, 才能使人信服這條路是可以走的吧! (看那精美的 Arxiv 論文下載, 有多少國外頂尖學者樂於在投稿前就將論文放上去!!)

今天想要分享的是 graph separators, 也是這一年來專注在學習的工具. 從 planar graphs 的演算法論文中, 總是看到它的身影; 慢慢的了解到, 這對平面圖(或是其他性質相似的圖)來說, separators 是個多麼強大的工具!
首先我們來定義 separator:

一個 $f(n)$ -separator 是個點集 $S$ , 滿足
1) 每個 $G \setminus S$ 的 connected component 大小都小於 $\alpha \cdot n$ for some $1/2 \leq \alpha < 1$ ;
2) $S$ 本身的大小小於 $f(n)$ .

舉例來說, 一棵 binary tree 我們可以想像它有個 $1$ -separator. (Prove it!) 直覺來說, separator 其實就只是個 vertex cut, 能夠把圖切斷成好幾份, 只不過另外要求圖要切的 “夠平均”. (平均的條件來自於當 $S$ 將圖切為兩半, 一個 connected component 夠小時, 另一個一定要夠大)

這樣的東西能有什麼用處呢? 最主要在於它保證了有好的 separator 的圖就可以 divide-and-conquer, 也就是 “大事化小, 小事化無”. 我們只要先將圖用 separator 切開, 在小的圖上解掉原本的問題, 再將答案兜回原來的圖中就行了. 一般來說 separator 有兩種用法: 一是重複在每個 connected component 上繼續找 separator, 將圖切到只剩下幾個點 (俗稱 constant size), 在這麼少點的圖上我們可以事先把所有答案算出來存好, 然後慢慢兜回去得到答案; 另一種是將原先已經有的演算法時間改進. 舉例來說, 若原本的問題有一個 $T(n)$ 時間的解法, 如果我們能夠很快的得到 separators 將圖切到 $k$ 的大小, 然後在這上面解掉原本的問題; 因為總共會有 $n/k$ 個大小為 $k$ 的小圖, 因此總共要花費 $O(T(k)\cdot n/k)$ 的時間. 假設今天 $T(n) = O(n^2)$ , 那麼利用 separator 我們就會的得到一個 $O(nk)$ 的演算法了.

講了 separator 的用處, 但我們仍然不知道到底有什麼樣的圖(除了剛剛提到的 binary tree 以外)可以有好的 separator? 1977年 Lipton 跟 Tarjan 第一次展示了某類稍微複雜的圖都有好的 separator:

Planar Separator Theorem. [Lipton & Tarjan]
大小為 $n$ 的平面圖都有個 $\sqrt{n}$ -separator.

這告訴我們, 平面圖可以 divide-and-conquer! 當然, 這樣的宣稱是很霸道的; 我們忽略了好幾個細節, 現在要來補充一下. 首先就是, 這樣的 separator 要花多久的時間才能找到? 在同一篇論文中, 他們證明存在一個 $O(n)$ 時間的演算法找到一個 separator; 這樣子應該能滿足大部分的需求了. 等等! 在我們剛剛的應用中, 常常都要對切開後剩下的 connected components 再遞迴的找 separators 直到圖被切得夠小, 這樣總共要花多少時間呢? 根據 separator 能夠 “平均” 的切開圖的性質, 我們知道這樣切開的動作最多只會有 $O(\log n)$ 層; 換句話說, 總共的時間會是 $O(n \log n)$ . 對於這樣時間還是不滿意的, Goodrich 提出了 separator decomposition, 能夠在 $O(n)$ 的時間內同時得到所有的 separators, 厲害吧!

再來就是, 找到的 separator 會不會長相太醜, 使得對某些問題來說, 當在小圖上解完之後卻沒有辦法兜回大圖的答案? 這時我們會希望 separator 本身有一些好的性質, 讓答案比較容易兜回去. Miller 發現到, 平面圖上的 separator 會有個好性質: 它可以是個 simple cycle!! 我們稱之為 cycle separator, Miller 的論文中同時也證明了能在 $O(n)$ 時間就找到這樣的 separator. 爾後, Alon, Seymour and Thomas 給出了 cycle separator 存在的簡單證明.

最後的問題就是: 平面圖實在是太特殊了, 有沒有其他的圖也能有好的 separator 呢? 同樣由 Alon, Seymour 和 Thomas 證明了: 任意圖只要不擁有某個 H-minor, 則就會有個 $(|H|^{2/3}n^{1/2})$ -separator. 當 $H$ 是某個固定的 $K_h$ 時, 我們有個 $O(n^{1/2}m)$ 時間的演算法. 這樣的圖可多了; 像是能夠 embed 在 constant genus 表面上的圖, 或是 bounded treewidth 的圖, 通通都會有 separator!!

到此為止, 我們對 separator 的概念有了初略的認識. 剩下的就是:
1) 有什麼直覺的方式能夠展示 Planar Separator Theorem 是正確的?
2) 由 separator theorem 衍伸出去有什麼樣的工具能拿來用?
3) separator 用在實際的問題上長什麼樣子?
在之後的介紹會一個個來提及!

Finite Playground

To verify is human; to prove, divine.

Tag Archives: separator

Graph Separators (1)