請問求一個圖的全局最小割，有什麼比較快的演算法？

01-14

算是個比較好搜的題目，憑經驗搜一下就好了……
隨便寫點翻譯好了……（只會常用的，捂臉

一個無向圖 $G = (V, E)$ 的割 $(S, T)$ 滿足 $S cup T = V, S eq emptyset, T eq emptyset$ ，這個割的代價是 $w(S, T) = sum_{u in S, v in T, u v in E}{w(uv)}$ 。而 $s - t$ 割則是滿足 $s in S, t in T$ 的全局割 $(S, T)$ 。對於這樣的圖，割一共有 $2^{|V| - 1} - 1$ 種，最小割是其中代價最小的某一個割。為了將割與 $s - t$ 割區分開來，有時也稱割為全局割。
一、我會暴力！
如果這個無向圖不連通，那麼全局最小割是很簡單的，否則由最大流最小割定理可知，求解 $s - t$ 最小割的對偶問題是求解 $s$ 為源點、 $t$ 為匯點的最大流問題，存在許多多項式時間的演算法可以解決。注意到 $s - t$ 最小割本身就是一個全局割，那麼全局最小割一定會是某一種 $s - t$ 最小割，求解全局最小割最暴力的確定性演算法就是隨便固定一個點 $s$ ，枚舉 $mathcal{O}left(|V| ight)$ 種可能的 $t$ ，分別求解 $s - t$ 最小割。
二、我會隨機！

Karger『s algorithm是這樣一個怪力亂神的隨機演算法：每次隨機時，它會不斷地從剩下的圖中選出一條邊，將這條邊的兩個端點縮在一起，直到整個圖剩下兩個端點，那麼原圖中分別被縮到這兩個端點的那些點分別構成了 $S$ 集和 $T$ 集，對應的割也可以直接從圖中求得。
每次隨機的時間複雜度是 $mathcal{O}(|E|)$ 的，隨機 $mathcal{O}left(|V|^2 log |V| ight)$ 次之後還沒有找到全局最小割的概率小於 $frac{1}{|V|}$ 。
他們順便擴展了一下這個演算法，每次隨機兩次將點集的大小縮到原來的 $frac{1}{sqrt{2}}$ ，分別遞歸求解相同問題，取最優值作為結果。他們表示這樣可以在 $mathcal{O}left(|V|^2log^3 |V| ight)$ 的時間裡以出錯可能小於 $frac{1}{|V|}$ 的概率找到全部最小割。
&不過，直接隨機選 $(s, t)$ 點對求最大流不就好了嗎？&
三、我會演算法！

Stoer—Wagner algorithm是這樣一個奧妙重重的確定演算法：每次嘗試得到當前圖中某兩個特殊點之間的 $s - t$ 最小割，將它們縮成一個點，直到整個圖縮成一個點，全局最小割即這個過程中計算過的 $s - t$ 最小割中的最小值。（？？？這複雜度不是暴力嗎？
與直接做 $mathcal{O}left(|V| ight)$ 次 $s - t$ 最小割不同的是，該演算法中使用的 $s$ 和 $t$ 是在求解過程中確定的，而不是直接給定的。
每次在當前的無向圖 $G$ 中不斷維護一個點集 $A$ ，初始點集 $A$ 包含一個任選的點 $u in V$ ，當 $A$ 時選取 $v in V$ 且 $sum_{u in A$ 最大的點 $v$ 加入點集 $A$ ，直到 $A$ 時結束，此時令倒數第二次加入 $A$ 的點為 $s$ ，最後一次加入 $A$ 的點為 $t$ ，則 $s - t$ 最小割為割 $(A$ 。正確性的話，證明其他 $s - t$ 割都不比它小就好了。
縮點一供要縮 $|V| - 1$ 次，每次找 $(s, t)$ 可以做到時間複雜度 $mathcal{O}left(|E| + |V|^2 ight)$ 或者 $mathcal{O}left(left(|E| + |V| ight) log |V| ight)$ 。
四、圖是平面圖！

由平面圖的對偶定理可知，原圖的每一個割都對應著新圖的每一個環，所以求解原圖中的 $s - t$ 最小割可以通過一些簡單的對偶變成求解對偶圖中的最短路問題。
而對於求解全局最小割，我們也可以使用分治的方法在對偶圖中求解最小環。每次在對偶圖中任選一個點 $a$ 為源點，構建對偶圖的最短路樹，再在對偶圖中找到一個區域 $F$ （對應原圖中的點 $f$ ）以及與它鄰接的兩個點 $b$ 和 $c$ ，令 $a, b, c$ 之間的這個環是 $C$ （即 $ab$ 最短路徑、 $ac$ 最短路徑、使 $F$ 被包含在 $C$ 內部的那條在 $F$ 上 $bc$ 之間的路徑），將原圖根據 $C$ 的內部與外部劃分成兩個部分（不含 $C$ ），給這兩部分分別加一個新點代表 $C$ ，即可遞歸求解不跨越 $C$ 的最小環，否則若要經過 $C$ ，則可以找到 $a$ 到 $b$ 路徑上的第一條邊所鄰接的不在 $C$ 內部的那個區域 $F$ （對應原圖中的點 $f$ ），可證原圖的全局最小割一定不會將 $f$ 與 $f$ 歸在同一點集，那麼只需要求解 $f - f$ 最小割就好了。
注意到平面圖有 $mathcal{O}left(|V| ight) = mathcal{O}(|E|)$ ，隨手寫一下的時間複雜度是 $mathcal{O}left(|V| log^2 |V| ight)$ 的，再努努力優化一下應該可以做到 $mathcal{O}left(|V| log log |V| ight)$ ，具體請參考ftiasch 的回答 - 平面圖最小環。（順手 at 卡不掉錯誤演算法的@趙軒昂）
五、我不管全局最小割了！我要多次詢問 $s - t$ 最小割！

這可能就有點超出能力範圍了？
&我還是老老實實做 $mathcal{O}left(|V|^2 ight)$ 次 $s - t$ 最小割吧……&
不要慌，我覺得還行！
這裡要介紹一個求解 $|V| - 1$ 次 $s - t$ 最小割的方法Gomory—Hu tree，做法很簡單，證明個人認為需要想一會。
對於一個連通無向圖 $G = (V, E)$ ，我們嘗試構建一個新的樹 $G$ ，其中 $V$ 中的元素是由 $V$ 中一些點組成的點集（即元素是集合），初始 $G$ ，我們將不斷地把 $G$ 中的點分裂，直到最終 $V$ 中的每一個元素都是 $V$ 中某一個點組成的點集並在兩者之間能形成雙射，此時求解 $s - t$ 割即計算 $G$ 中點 ${s}$ 到點 ${t}$ 路徑上的最小邊權值。
分裂是指每次選擇一個點集 $A in V$ ，滿足 $A$ 中至少有兩個 $V$ 中的點，並從中選出兩個點 $s in A, t in A$ ，求解 $s - t$ 最小割 $(S, T)$ ，將 $A$ 劃分成 $A cap S, A cap T$ 兩個點，在它們之間連一條邊權值為 $w(S, T)$ 的邊，之前與 $A$ 相連的邊也根據另一個端點屬於 $S$ 或 $T$ 來確定連向 $A cap S$ 或 $A cap T$ 即可。
此外，Gomory—Hu tree 也經常作為近似求解 $k$ 連通塊最小割的演算法例子。

隨手寫的很倉促，不知道有什麼要補充的，待我趕完 deadline 再來修一修 T_T

2017年我們有個paper裡面的introduction里提到了這些. http://chaoxu3.web.engr.illinois.edu/paper/hypergraph.pdf
裡面除了Henzinger, Rao, Wang的那個都有reference. 這個introduction應該完全survey了有關的內容. 所以讀讀應該會了解到所有的情況.
(話說日本那邊對Stoer-Wagner不是很爽. 當時給talk的時候被Satoru Iwata教育了. 因為Nagamochi-Ibaraki更早的給出演算法了, 憑什麼大家都在cite那個Stoer-Wagner...
Deterministic還沒有. 哪個人能給出deterministic擊敗Stoer-Wagner的話那重要程度絕對是stoc/focs best paper級別.
randomized話 karger早就有了 $ilde{O}(m)$ 級別的演算法.
圖是simple graph, 則 $ilde{O}(m)$ 存在. 看Kawarabayashi和Thorup. 後來Henzinger, Rao, Wang 給了更快的演算法不過只是log級別的提升. (paper里沒有提到. 因為太新了. https://arxiv.org/abs/1704.01254)
圖是unweighted graph, 則可以先找k-certificate然後再用SW演算法. 可以O(m)時間把邊的個數變成O(kn)個. 所以k很小的話速度還蠻快的. 這樣 $ilde{O}(mn)$ 就是 $O(kn^2)$ . paper的survey裡面應該還列舉了一些其他的比如Gabow的 $O(m+nk^2)$ 的演算法.
有向圖要用Hao-Orlin是暫時最快的. 我不記得Gabow是不是在log上面稍微擊敗了Hao-Orlin.
以及open problem: 圖的全局最小的非平凡割?

推薦閱讀：