## 收缩操作

The contraction operator Contract(G, e)

say e = uv:

• replace $\{u,v\}$ by a new vertex x;
• for every edge (no matter parallel or not) in the form of $uw$ or $vw$ that connects one of $\{u,v\}$ to a vertex $w\in V\setminus\{u,v\}$ in the graph other than $u,v$, replace it by a new edge $xw$;
• the reset of the graph does not change.

## Karger’s algorithm

### 简单的idea

• 在当前的multi-graph中每一步随机选择一条边来收缩直到最终仅剩下两个点为止

• 这两个点之间的并行边一定是这个原始图的一个Cut

• 我们返回这个Cut并且希望有很大几率这个Cut是minimum-Cut

### 伪代码

RandomContract (Karger 1993)

Input: multi-graph G(V,E);

while | V | > 2 do

choose an edge ${uv}\in E$ uniformly at random;

G = $Contract(G,uv)$;

return C = E (the parallel edges between the only two vertices in V);

## 精度分析

### 分析

$$\begin{array} {lcl} p_C & = & Pr[ C\ is\ returned\ by\ RandomContract] \\ & = & Pr[e_i \notin C for\ all\ i = 1,2,\ldots, n-2] \\ & = & \prod_{i=1}^{n-2}Pr[ e_i \notin C \vert \forall j < i, e_j \notin C] \end{array}$$

$$\begin{array} {lcl} p_i & = & 1 - \frac{\vert C \vert}{\vert E_i \vert} \\ & \geq & 1 - \frac{2}{|V_i|} \\ & = & 1- \frac{2}{n-i+1} \end{array}$$

$$\begin{array} {lcl} p_{\text{correct}} & = & \Pr[\,\text{a minimum cut is returned by }RandomContract\,]\\ & \geq & \Pr[\,C\mbox{ is returned by }{RandomContract}\,]\\ & = & \Pr[\,e_i\not\in C\mbox{ for all }i=1,2,\ldots,n-2\,]\\ & = & \prod_{i=1}^{n-2}\Pr[e_i\not\in C\mid \forall j<i, e_j\not\in C]\\ & \geq & \prod_{i=1}^{n-2}\left(1-\frac{2}{n-i+1}\right)\\ & = & \prod_{k=3}^{n}\frac{k-2}{k}\\ & = & \frac{2}{n(n-1)}. \end{array}$$

## Fast Min-Cut

### 算法

• 预处理算法：RandomContract

RandomContract(G,t)

Input: multi-graph $G(V,E)$, and integer $t \ge 2$; while $| V | > t$ do

• choose an edge ${uv}\in E$ uniformly at random;
• $G = Contract(G,uv)$; return $G$;
• FastCut算法

FastCut(G)

Input: multi-graph $G(V,E)$;

if $|V|\le 6$ then return a mincut by brute force;

else let $t=\left\lceil1+|V|/\sqrt{2}\right\rceil$;

• $G_1$ = $RandomContract(G,t)$;
• $G_2$ = $RandomContract(G,t)$;
• return the smaller one of $FastCut(G_1)$ and $FastCut(G_2)$;

### 分析

$$\begin{array} {lcl} &\quad & \Pr[C\text{ survives all contractions in }RandomContract(G,t)]\\ & = & \prod_{i=1}^{n-t}\Pr[C\text{ survives the }i\text{-th contraction}\mid C\text{ survives the first }(i-1)\text{-th contractions}]\\ & \ge & \prod_{i=1}^{n-t}\left(1-\frac{2}{n-i+1}\right)\\ & = & \prod_{k=t+1}^{n}\frac{k-2}{k}\\ & = & \frac{t(t-1)}{n(n-1)}. \end{array}$$

FastCut过程:

p(n)为C被FastCut(G)返回的概率：

$$\begin{array} {lcl} p(n) & = & \Pr[C\text{ is returned by }\textit{FastCut}(G)]\\ & = & 1-\left(1-\Pr[C\text{ survives in }G_1\wedge C=\textit{FastCut}(G_1)]\right)^2\\ & = & 1-\left(1-\Pr[C\text{ survives in }G_1]\Pr[C=\textit{FastCut}(G_1)\mid C\text{ survives in }G_1]\right)^2\\ & \ge & 1-\left(1-\frac{1}{2}p\left(\left\lceil1+n/\sqrt{2}\right\rceil\right)\right)^2, \end{array}$$

$$p(n)=\Omega\left(\frac{1}{\log n}\right).$$

$$T(n)=2T\left(\left\lceil1+n/\sqrt{2}\right\rceil\right)+O(n^2),$$

$T(n) = O(1)\ for\ n\le 6$, 因此$T(n) = O(n^2logn)$.