COMP5270 Assignment 2 Problem 1, Karger 算法列出所有最小割
COMP5270 Assignment 2 Problem 1, Karger 算法列出所有最小割
中文题目
简要说明如何修改 Karger 算法，使它能够以高概率（例如 99%）列出一个图的所有最小割（minimum cuts）。同时分析你的算法时间复杂度。
原题
Briefly explain how to modify Karger’s algorithm to list, with high probability (say 99%), all minimum cuts of a graph. What is the time complexity of your algorithm?
知识点
- Karger contraction algorithm
- minimum cut / global min-cut
- 随机算法重复放大成功概率
- union bound
- 最小割数量上界
- 高概率枚举（high-probability enumeration）
核心思路
普通的 Karger contraction algorithm 一次运行，只会随机输出一个 cut。要把它改成“列出所有 minimum cuts”，最直接的方法不是改 contraction 过程本身，而是：
- 独立重复运行 Karger 算法很多次
- 每次得到一个 cut 后，计算它的 cut size
- 维护当前见过的最小 cut size
- 只保留所有大小等于这个最小值的 cuts
- 对这些 cuts 做 去重，最后输出去重后的结果集合
换句话说，这里真正的修改是把“单次随机输出一个最小割候选”变成“多次采样并收集所有采样到的 minimum cuts”。
为什么这样能找到所有 minimum cuts
Karger 算法的经典结论是，对于一个有 \(n\) 个顶点的图，任意一个固定的 minimum cut 在一次运行中被输出的概率至少为
\[ \frac{2}{n(n-1)}. \]
设某个特定 minimum cut 为 \(C\)。如果我们独立运行算法 \(r\) 次，那么一次都没有采到 \(C\) 的概率至多为
\[ \left(1-\frac{2}{n(n-1)}\right)^r. \]
当 \(r = \Theta(n^2 \log n)\) 时，这个概率会下降到非常小。
另一方面，一个图的 minimum cuts 总数至多为
\[ \binom{n}{2} = \frac{n(n-1)}{2}. \]
所以我们可以对所有 minimum cuts 使用 union bound。只要把重复次数取成足够大的 \(c n^2 \log n\)，就能保证“漏掉至少一个 minimum cut”的总概率低于 \(1\%\)，也就是以至少 99% 的概率列出全部 minimum cuts。
算法描述
可以写成下面这个版本：
- 设
best = +∞，设集合S = ∅ - 重复运行 Karger 算法 \(r = \Theta(n^2 \log n)\) 次
- 每次得到 cut \(C\)，记其大小为 \(|C|\)
- 如果 \(|C| < best\)，则更新
best = |C|，并把S重置为只包含 \(C\) - 如果 \(|C| = best\)，则把 \(C\) 加入
S - 对 cuts 做规范化表示并去重，例如始终把一个 cut 表示成两侧顶点集里较小字典序的一侧，避免同一个 cut 被重复存储
- 输出
S
时间复杂度
如果一次 Karger 运行耗时记为 \(O(n^2)\)，而我们总共运行
\[ O(n^2 \log n) \]
次，那么总时间复杂度就是
\[ O(n^2) \cdot O(n^2 \log n) = O(n^4 \log n). \]
去重带来的额外开销不会改变这个主导复杂度，因此最终时间复杂度仍然是
\[ \boxed{O(n^4 \log n)}. \]
可以直接交作业的短答案
Run Karger’s algorithm independently \(O(n^2\log n)\) times, keep every cut whose size equals the minimum found, and deduplicate them. Since each fixed minimum cut is found with probability at least \(2/(n(n-1))\), and there are at most \(n(n-1)/2\) minimum cuts, this lists all minimum cuts with probability at least \(99\%\). If one run takes \(O(n^2)\), the total running time is \(O(n^4\log n)\).
一点补充理解
这道题的关键不是设计一个全新的算法，而是把 Karger 的“单个最小割采样器”升级成“最小割全集收集器”。核心工具只有两个：
- 单个 minimum cut 的命中概率下界
- minimum cut 总数的上界，加上 union bound
所以这题本质上是在考，你会不会把一个 randomized existence guarantee，转成一个 high-probability enumeration guarantee。