Undirected Minimum Cut Algorithm

個人的メモ

グラフ $G = (V, E)$ についてある頂点 $v \in V$ から始めて今の頂点集合 S と一番連結度の高い頂点を $S$ に加えていくというように貪欲に取っていく順序を最大隣接順序 (MA ordering) と呼ぶ.
このとき, 最大隣接順序での後ろ 2 つの頂点 $x_n, x_{n-1}$ の間の連結度($x_n, x_{n-1}$ 間最小カット)が $x_n$ の重みつきの次数($\delta (x_n)$)に一致する(事実自体は驚きだが, 帰納法から比較的簡単に示せる). これによって $2$ 点間の連結度が陽に分かったので $x_n$ と $x_{n-1}$ の $2$ 点を縮約することができる. 具体的には縮約後のグラフを $G'$ とすると解となる最小カット $S^{\ast}$ で $x_n, x_{n-1}$ が分かれるか分かれないかを考えて大域最小容量カットは $\min (\delta(x_n), \lambda(G'))$ となる. この操作を $1$ 点になるまで繰り返すことで大域最小容量カットが得られる.
このアルゴリズムはより一般的な(対称)劣モジュラ関数の最小化アルゴリズムに拡張される(Queyranne 1998).
計算量については MA 順序を FibonacciHeap を用いることで $\O(m + n \log n)$ 時間で求めることができ, また各回の縮約操作も $\O(m)$ 時間で行うことができるので全体で $\O(mn + n \log n)$ 時間となる.

(補足 1)
重みなし大域最小容量カットの場合は, 何も考えずグラフの辺をランダムに縮約していき残り $2$ 点になったときの連結度を最小容量カットの候補とするというような操作を $\Theta (n^2)$ くらい繰り返せばある程度の確率で最適解が得られるというようなモンテカルロアルゴリズムも存在する. 以下 Rajeev Motwan, Prabhakar Raghavan の Randomized Algortihms の第 $1$ 章に書いている証明にもとづく.
やることは 「グラフ内の辺を適当に $1$ つ選んで縮約するという操作を頂点が $2$ 点になるまで繰り返し, 最後の $2$ 頂点間に張られている辺の数を暫定の最適なカットとする.」 という操作を $\Theta (n^2)$ くらい繰り返すことである. 縮約の際に注目している $2$ 頂点間に張られている辺は取り除くことにする. このとき observation として "縮約後のグラフにおけるカットは縮約前のグラフにおいてもカットとなっている" ということが成り立つため最後の $2$ 頂点間に張られている辺の数は最小カットの候補として問題ないことが分かる. 以下では $1$ 回の操作で最小カットが得られる確率, 言い換えると最小カットに含まれる辺が縮約されることがない確率が $2 / (n (n - 1))$ 以上となることを示す. これが示せると後は Chernoff bound から $\O (n^4 \log n)$ 時間, w.h.p で重みなし最小容量カットを求めるアルゴリズムが得られる.
最小カットを $S^{\ast}$ とし、 $k = |(S^{\ast}, V \setminus S^{\ast})|$ とする. このとき明らかにグラフには $k n / 2$ 本以上の辺が存在する. ここから $1$ 本ランダムに辺を選んできたときにその辺が $(S^{\ast}, V \setminus S^{\ast})$ に含まれている確率は $2 / n$ 以下であることがわかる. 縮約後のグラフについては前述のように最小カットの値は $k$ 以上となるため $k (n - 1) / 2$ 本以上の辺が存在し, ここから $1$ 本ランダムに辺を選んできたときにその辺がカットに含まれている確率は $2 / (n - 1)$ 以下であることがわかる. これを繰り返して全 $n - 2$ 回の縮約の間最小カットに含まれる辺が縮約されない確率は $2 / (n (n - 1))$ 以上となり示せた.
重みつきグラフの場合はグラフの辺をその重さに比例する確率でランダムにサンプリングして縮約していくことで同じように 1 回の試行で $\Omega (n^{-2})$ の確率で大域最小カットが得られることが言える.
余談として重みなし大域最小カットの集合を $C$ とすると, 任意の大域最小カット $c \in C$ について上記の乱択アルゴリズムによって最終的にカット $c$ に対応する辺が残る確率は $2 / (n (n - 1))$ 以上であることが分かるので $C$ のサイズ, つまり大域最小カットの個数は高々 $2 / (n (n - 1))$ 個である. $n$ 頂点のサイクルがこの upper bound を達成するため tight である.

(補足 2)
他にも有名なものとして $\O (n^2 \log^3 n)$ 時間, w.h.p で重みつき大域最小容量カットを求める乱択アルゴリズムもある. 元論文は "A New Approach to the Minimum Cut Problem" (Karger, Stein 1996)
これは上記のアルゴリズムにおける縮約の際に $i$ 頂点のグラフなら最小カットに含まれる辺が縮約されない確率は $2 / i$ くらいということから特に縮約の後半において失敗しやすいことが分かる. よって縮約の前半パートと後半パートで試行回数を前者を少なく, 後者を多くするといった頭のいい方法が考えられる. 具体的に Rec$(G, n)$ を $n$ 頂点のグラフ $G$ の最小カットを求める乱択アルゴリズムとすると, その内容は次の操作を $2$ 回行うというものである.
"$n$ 頂点のグラフ $G$ を $n / \sqrt{2}$ 頂点のグラフ $G'$ にランダムに縮約し, Rec$(G', n / \sqrt{2})$ を行う."
このとき Rec$(G, n)$ が成功する確率 $P(n)$ について $P(n) = 1 - \left( 1 - P(n / \sqrt{2}) / 2 \right)^2$ が成り立つ. これは "$G'$ への縮約が成功しかつ Rec$(G', n / \sqrt{2})$ が成功する" という事象が $2$ 回のうち少なくとも一方で起こる確率を表している. 一般に $n$ 頂点のグラフから $k$ 頂点のグラフへの縮約が成功する(ある fix された大域最小カットが縮約によって消えない)確率は $\Omega ((k / n)^2)$ であることが (補足 1) の確率評価と同じようにして示せることに注意する. よって $P(n) = \Omega(\log^{-1} n)$ が言える.
また $1$ 回の試行にかかる時間 $T(n)$ は $T(n) = 2 T(n / \sqrt{2}) + \O (n^2)$ より $\O (n^2 \log n)$ であることが分かる. よってこれを $\log^2 n$ 回ほど繰り返すと計算時間 $\O (n^2 \log^3 n)$ 時間, w.h.p で重みつき大域最小容量カットが求まる.

(補足 3)
無向グラフの大域最小容量カットを求めるアルゴリズムは近年でもよく研究されていて deterministic algorithm として $\O (m \log^{12} n)$ (Kawarabayashi, Thorup 2014) (初の nearly linear time), $\O (m \log^2 n \log \log^2 n)$ (Henzinger, Rao, Wang 2017) (unit flow(push relabel の高さを制限した局所的な flow routing) を用いることで low conductance cut を求める部分を高速化した) などがある. 重みつきの場合は randomized algorithm として $\O (m \log^3 n)$ (Karger 2000, announced at STOC '96) がある.
$k$ "点"連結性判定についても時間計算量 $\O (m + nk^3)$ (SODA '20) のモンテカルロアルゴリズムが発表された.