一句話解釋

隨機選邊並收縮（contract），重複到剩兩個節點，剩下的邊就是候選割；成功率約 $\frac{2}{n^2}$，重複 $O(n^2 \log n)$ 次可高機率成功。

問題定義：Min-Cut

問題設定

最小割（Minimum Cut）

給定無向圖 $G = (V, E)$：

  • 割（Cut）： 將頂點集 $V$ 分成兩個非空子集 $S$ 和 $T = V \setminus S$
  • 割的大小： 連接 $S$ 和 $T$ 的邊數
  • 最小割： 所有割中大小最小的
$$ \text{Min-Cut}(G) = \min_{S \subset V, S \neq \emptyset, V} |\{(u,v) \in E : u \in S, v \in V \setminus S\}| $$

應用

  • 網路可靠性： 最小割 = 切斷網路的最少邊數
  • 圖像分割： 將影像分成前景與背景
  • 社群檢測： 找出社交網路的分群

確定性演算法

  • Max-Flow Min-Cut： $O(mn)$ 或更好（但需選擇 source-sink 對）
  • Stoer-Wagner： $O(mn + n^2 \log n)$，確定性找全局最小割

Karger 的演算法更簡單，且對某些問題（如找所有近似最小割）更有效。

Karger’s 演算法

Edge Contraction

核心操作：邊收縮（Edge Contraction）

Contraction（收縮） 一條邊 $(u, v)$：

  1. 將 $u$ 和 $v$ 合併成一個新節點（超節點）
  2. 所有連到 $u$ 或 $v$ 的邊，都改連到新節點
  3. 移除自環（self-loops）

範例：
圖 $G$ 有邊 $(u, v)$，收縮後：

  • $u$ 和 $v$ 變成單一節點 $w$
  • 原本的 $(u, x)$ 和 $(v, y)$ 變成 $(w, x)$ 和 $(w, y)$
  • 如果 $u$ 和 $v$ 之間有多條邊，收縮後變成自環（被移除）

演算法流程

Algorithm: Karger's Min-Cut
Input: 無向圖 $G = (V, E)$，$|V| = n$
Output: 一個割（候選最小割）
  1. **While** 圖還有超過 2 個節點：
    • a. 隨機均勻選擇一條邊 $e \in E$
    • b. 收縮 $e$（將兩端點合併）
  2. **Return** 剩下的兩個超節點之間的所有邊（這是候選割）

關鍵觀察

  • 每次收縮減少一個節點：$n \to n-1 \to \cdots \to 2$
  • 總共收縮 $n-2$ 次
  • 每次收縮都是隨機選擇，所以最終結果是隨機的

💡 為什麼可能成功？
如果我們從未收縮最小割中的邊，最後剩下的邊就是最小割！
問題是：這件事的機率有多大？

成功率分析

機率分析

定理

Theorem: 對於有 $n$ 個節點的圖 $G$，Karger 演算法找到最小割的機率**至少**為： $$ \Pr[\text{成功}] \geq \frac{2}{n(n-1)} \geq \frac{2}{n^2} $$

證明思路

令 $C$ 是最小割，$ C = k$（最小割的大小）。

目標： 證明 $\Pr[\text{沒有收縮到 } C \text{ 中的邊}] \geq \frac{2}{n^2}$

Step 1: 每個節點的度數下界

因為最小割大小是 $k$，每個節點的度數至少是 $k$（否則該節點自己形成的割更小）。 $$ \deg(v) \geq k, \quad \forall v \in V $$ 因此總邊數： $$ |E| \geq \frac{nk}{2} $$

Step 2: 第一次收縮不碰到 min-cut 的機率

第一次隨機選邊，選到 $C$ 中的邊的機率： $$ \Pr[\text{選到 } C] = \frac{k}{|E|} \leq \frac{k}{nk/2} = \frac{2}{n} $$ 所以**不選到** $C$ 的機率： $$ \Pr[\text{不選到 } C] \geq 1 - \frac{2}{n} = \frac{n-2}{n} $$

Step 3: 第 $i$ 次收縮

在第 $i$ 次收縮時，還剩 $n-i+1$ 個（超）節點。 關鍵： 最小割仍是 $k$（收縮不會減少最小割的大小，只要我們沒碰到它）。 邊數至少：$\frac{(n-i+1) \cdot k}{2}$ 不選到 $C$ 的機率： $$ \Pr[\text{第 } i \text{ 次不選到 } C \mid \text{前 } i-1 \text{ 次都沒選到}] \geq \frac{n-i-1}{n-i+1} $$

Step 4: 連鎖機率

所有 $n-2$ 次收縮都不選到 $C$ 的機率： $$ \begin{align} \Pr[\text{成功}] &= \prod_{i=1}^{n-2} \Pr[\text{第 } i \text{ 次不選到 } C \mid \text{前面都沒選到}] \\ &\geq \prod_{i=1}^{n-2} \frac{n-i-1}{n-i+1} \\ &= \frac{n-2}{n} \cdot \frac{n-3}{n-1} \cdot \frac{n-4}{n-2} \cdots \frac{2}{4} \cdot \frac{1}{3} \\ &= \frac{2 \cdot 1}{n \cdot (n-1)} = \frac{2}{n(n-1)} \end{align} $$

🎯 結論：
單次執行成功率約 $\frac{2}{n^2}$。雖然很小，但多項式級別（不是指數小）！
這意味著重複多項式次就能高機率成功。

重複策略

提升成功率

重複執行

單次成功率 $p \geq \frac{2}{n^2}$，失敗率 $1-p \leq 1 - \frac{2}{n^2}$。

執行 $k$ 次，全部失敗的機率：

$$ \Pr[\text{全部失敗}] = (1-p)^k \leq \left(1 - \frac{2}{n^2}\right)^k $$ 利用不等式 $1-x \leq e^{-x}$： $$ \Pr[\text{全部失敗}] \leq e^{-2k/n^2} $$

選擇重複次數

要達到成功率 $\geq 1 - \delta$： $$ e^{-2k/n^2} \leq \delta \quad \Rightarrow \quad k \geq \frac{n^2}{2} \ln \frac{1}{\delta} $$ 常見選擇： - $\delta = 1/n$：$k = O(n^2 \log n)$，成功率 $\geq 1 - 1/n$ - $\delta = 0.01$：$k = O(n^2)$，成功率 $\geq 99\%$

總時間複雜度

- 單次執行： $O(n^2)$（$n-2$ 次收縮，每次 $O(n)$） - 重複 $k$ 次： $O(k \cdot n^2) = O(n^4 \log n)$（若 $k = O(n^2 \log n)$） 改進版（Karger-Stein）： $O(n^2 \log^3 n)$，用遞迴策略

範例

簡單例子

考慮 4 個節點的環狀圖：

A --- B
|     |
D --- C

最小割大小 = 2（例如切掉 AB 和 CD）。

執行過程（一個可能的情況）：

  1. 隨機選 AB，收縮 → 剩 3 個超節點
  2. 隨機選 BC，收縮 → 剩 2 個超節點
  3. 剩下的邊 = {AD, CD}（不是最小割，失敗）

成功情況： 如果一直不選 AB 和 CD（假設它們是最小割的邊），最後剩下這兩條邊 → 成功！

成功率：$\frac{2}{4 \times 3} = \frac{1}{6} \approx 16.7\%$

總結

Karger’s Min-Cut 是隨機演算法的經典範例：

  1. 極簡演算法： 隨機選邊、收縮、重複
  2. Monte Carlo 類型： 多項式時間，但可能失敗
  3. 成功率分析： 單次 $\geq \frac{2}{n^2}$，看似小但夠用
  4. 重複策略： $O(n^2 \log n)$ 次 → 高機率成功
  5. 總複雜度： $O(n^4 \log n)$（樸素版）

關鍵技巧： 機率分析中的連鎖機率、Union Bound、以及 amplification by repetition。

參考資料

  • Karger, “Global Min-Cuts in RNC and Other Ramifications of a Simple Min-Cut Algorithm”, 1993
  • Karger & Stein, “A New Approach to the Minimum Cut Problem”, 1996
  • Motwani & Raghavan, Randomized Algorithms, Chapter 10