CS521 Advanced Algorithm Design 学习笔记（二）Karger’s Min Cut Algorithm

Lecture 2 Karger’s Min Cut Algorithm

给定图G，求图中的最小割，即min⁡SE(S,S‾)\\min_S E(S,\\overline{S})minS​E(S,S). 这个问题很容易被最大流问题解决，所以是polynomial的。但是我们这里给出Karger的随机算法。

思路：每次选取一个随机边，并且将其端点融合为一个“超点”，重复这一过程直到只剩下两个超点，我们将其输出为对min-cut的猜测。为什么这个过程可行呢？一个直觉是随机选边的时候一定更有可能选到边比较密的地方，而它们确实就是应当融合的边。

今天我们会首先学习一个至少以2/n22/n^22/n2的概率输出mincut的算法。显然，如果我们只是平凡地重复20n220n^220n2次，那么虽然成功概率很高，但是算法复杂度高达O(n4)O(n^4)O(n4). 因此，我们需要采取称为”repetition ensures fault tolerance”（竞争容错法）来把算法降低到O(n2)O(n^2)O(n2). 我们注意到，虽然运行这个算法直到剩下两个超点的成功概率很低，但是如果我们只运行到剩下n/2n/\\sqrt{2}n/2​个超点就停下，那么它保留了mincut的概率是$1/2$. 这样，我们让两个算法同时运行到n/2n/\\sqrt{2}n/2​，然后挑一个最好的，然后重复上面的过程。可以证明，这样的重复竞赛会得到一个成果概率超过$1/\log n$的算法。

为了分析这个算法的效果，我们给出下列引理：

1. 图中顶点的度数和是边数的两倍：∑vd(v)=2∣E∣\\sum_v d(v)=2|E|∑v​d(v)=2∣E∣

2. mincut中至多有$2|E|/n$条边

   简证：至少有一个顶点的度数至多为$2|E|/n$，把这个点和其他点割开即可

3. 随机选取一条边，其穿过mincut的概率至多为$2/n$.

   简证：引理2+图中一共有$|E|$条边。

4. 同理，当图中只剩下k个超点时，随机选取一条边，穿过mincut的概率至多为$2/k$

   简证：假设现在图中有$t$条边，则mincut的边数至多$2t/k$.

5. Karger算法得到最小割的概率至少为$2/n(n-1)$

   证明：
   Pr⁡(final cut is the minimum cut )=Pr⁡(first selected edge is not in mincut )×Pr⁡(second selected edge is not in mincut )×⋯≥(1−2n)(1−2n−1)(1−2n−2)⋯(1−24)(1−23)=n−2n⋅n−3n−1⋅n−4n−2⋯24⋅13=2n(n−1).\\begin{aligned} & \\operatorname{Pr}(\\text { final cut is the minimum cut }) \\\\= & \\operatorname{Pr}(\\text { first selected edge is not in mincut }) \\times \\\\ & \\operatorname{Pr}(\\text { second selected edge is not in mincut }) \\times \\cdots \\\\ \\geq & \\left(1-\\frac{2}{n}\\right)\\left(1-\\frac{2}{n-1}\\right)\\left(1-\\frac{2}{n-2}\\right) \\cdots\\left(1-\\frac{2}{4}\\right)\\left(1-\\frac{2}{3}\\right) \\\\ = & \\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}{n(n-1)} . \\end{aligned} =≥==​Pr( final cut is the minimum cut )Pr( first selected edge is not in mincut )×Pr( second selected edge is not in mincut )×⋯(1−n2​)(1−n−12​)(1−n−22​)⋯(1−42​)(1−32​)nn−2​⋅n−1n−3​⋅n−2n−4​⋯42​⋅31​n(n−1)2​.​
   我们注意到，如果做$l$次就停下来的话，算法的成功概率为：

(1−2n)(1−2n−1)(1−2n−2)⋯(1−l−2l)=2n(n−1)l(l−1)2\\left(1-\\frac{2}{n}\\right)\\left(1-\\frac{2}{n-1}\\right)\\left(1-\\frac{2}{n-2}\\right) \\cdots\\left(1-\\frac{l-2}{l}\\right)\\\\=\\frac{2}{n(n-1)}\\frac{l(l-1)}{2} (1−n2​)(1−n−12​)(1−n−22​)⋯(1−ll−2​)=n(n−1)2​2l(l−1)​

特别地，取l=n/2l=n/\\sqrt{2}l=n/2​，则成功概率大于等于1/2.

算法：

for round=1,2:run the Karger's algorithm down to n/sqrt{2}+1 verticesrucurse on the resulting graph
return the minimum of the cuts found in two rounds

使用主定理，我们有T(n)=2(n2+T(n/2))=O(n2log⁡n).T(n)=2(n^2+T(n/\\sqrt{2}))=O(n^2 \\log n).T(n)=2(n2+T(n/2​))=O(n2logn).

假设顶点数量为n时成功概率为$P(n)$，则：
P(n)≥1−(1−12P(n/2+1))2P(n)\\geq 1-(1-\\frac{1}{2} P(n/\\sqrt{2}+1))^2 P(n)≥1−(1−21​P(n/2​+1))2
可以解得$P(n)=\Omega (1/\log n)$

从而，我们可以重复运行O(log⁡n2)O(\\log n^2)O(logn2)次算法，以至多O(n2log⁡3n)O(n^2 \\log^3 n)O(n2log3n)次运行，算法有成功概率$1-1/poly(n)$.

推论：一个图中至多有$n(n-1)/2$个mincut

证明：注意到引理5对任意mincut均成立。所以，由于对每个mincut，算法得到它的概率都大于等于$2/n(n-1)$，图中至多只能有$n(n-1)/2$个mincut。考虑一个长为n的圈可以得知这个界是紧的。