最小割

给定一个连通图 $G = \left(V, E\right)$。如果一个边子集 $C \subseteq E$ 是一个 割 当且仅当将 $C$ 中所有的边全部删除后，图不再连通。

所谓 最小割，就是让 $C$ 中的边权和最小。

Karger 算法

定义 收缩 操作 $\mathsf{Contract}\left(e\right)$：

  1. 设 $e = \left(u, v\right)$
  2. 把边 $u$ 和 $v$ 替换为一个新点 $x$
  3. 对于任何一条以 $u$ 为端点的边 $e' = \left(u, w\right)$，连接 $x$ 和 $w$
  4. 对于任何一条以 $v$ 为端点的边 $e' = \left(v, w\right)$，连接 $x$ 和 $w$
  5. 销毁点 $x$ 的所有自环

Karger 算法执行以下流程：

  1. 如果 $\left\lvert V \right\rvert \leq 2$，结束算法
  2. 随机选择一条边 $e \in E$
  3. $\mathsf{Contract}\left(e\right)$

此时只有不超过两个点，剩下的边的边权和即为答案。

正确率

我们先来看看 Karger 算法的正确率。

其实，Karger 算法的正确率不好分析，因为每次选择不是独立的。

考虑在固定任意一个合法的最小割 $C$ 时，Karger 算法恰好返回这个最小割 $C$ 的概率。

根据直觉，最小割是稀疏的。对于一个合法的最小割 $C$，图 $G$ 必须满足 $\left\vert E\right\rvert \geq \frac{\left\lvert V\right\rvert\left\lvert C\right\rvert}2$，因为每个点的度数至少得是 $\left\lvert C\right\rvert$，每两个度数对应一条边。

如果一次 收缩 操作选择的边 $e_i$ 被 $C$ 包含，则最终 Karger 算法不可能返回 $C$。

否则，$C$ 中的所有边全部被保留。根据 收缩 操作性质，$C$ 将会被返回。注意 收缩 操作不会创建新的割。

记 $G_i = \left(V_i, E_i\right)$ 表示第 $i$ 次操作前的图。

因此根据概率链式法则：

$$ \begin{aligned} \Pr\left[\text{Correct}\right] &\geq \Pr\left[\text{C is returned by Karger Algorithm}\right] \\ &= \Pr\left[e_i \notin C \text{ for all } i \leq n - 2\right] \\ &= \prod\limits_{1 \leq i \leq n - 2} \Pr\left[e_i \notin C \mid \forall j < i, e_j \notin C \right] \\ &= \prod\limits_{1 \leq i \leq n - 2}\frac{\left\lvert E_i\right\rvert - \left\lvert C\right\rvert}{\left\lvert E_i\right\rvert} \\ &\geq\prod\limits_{1 \leq i \leq n - 2}\frac{\frac{\left\lvert V_i\right\rvert\left\lvert C\right\rvert}2 - \left\lvert C\right\rvert}{\frac{\left\lvert V_i\right\rvert\left\lvert C\right\rvert}2} \\ &=\prod\limits_{1 \leq i \leq n - 2}\frac{\left\lvert V_i\right\rvert - 2}{\left\lvert V_i\right\rvert} \\ &=\prod\limits_{1 \leq i \leq n - 2}\frac{n - i - 1}{n - i + 1}\\ &= \frac2{n\left(n - 1\right)} \end{aligned} $$

如果我们运行 $\frac{n\left(n - 1\right) \log n}2$ 次，正确概率至少有

$$1 - \left(1 - \frac2{n\left(n - 1\right)}\right)^{\frac{n\left(n - 1\right) \log n}2} \geq \frac1n$$

足够优秀了。每次跑 Karger 的时间复杂度可以做到 $\tilde O\left(n^2\right)$，因此总复杂度为 $\tilde O\left(n^4\right)$。

推论

设 $\mathcal C$ 为所有可能的最小割的集合。

$$1 \geq \Pr\left[\text{Correct}\right] \geq \sum\limits_{C \in \mathcal C}\frac2{n\left(n - 1\right)} = \left\lvert\mathcal C\right\rvert\frac2{n\left(n - 1\right)}$$

因此，$\left\lvert\mathcal C\right\rvert \leq \frac2{n\left(n - 1\right)}$。

即对于一个 $n$ 个点的图，最多有 $n\left(n - 1\right) / 2$ 种不同的割。

优化

注意到在 $\left\lvert V\right\rvert$ 较小时，收缩操作很容易选择到 $C$ 中的边，从而让整个算法失败。

我们不妨让 $\left\lvert V\right\rvert$ 较小时多尝试几次。具体使用如下方法。

  1. 如果 $\left\lvert V\right\rvert \leq t$，停止操作。
  2. 随机选择一条边 $e \in E$
  3. $\mathsf{Contract}\left(e\right)$

这样，$C$ 中的边全部保留的概率至少为

$$\prod\limits_{1 \leq i \leq n - t}\frac{n - i - 1}{n -i + 1} = \frac{t\left(t - 1\right)}{n\left(n - 1\right)}$$

如果我们取 $t \geq \left\lceil n / \sqrt 2 + 1\right\rceil$，那么 $C$ 被全部保留的概率至少有 $1 / 2$。

于是我们的新算法如下。

  1. 如果 $\left\lvert V\right\rvert \leq 6$，使用暴力解决。
  2. 令 $t = \left\lceil 1 + \left\lvert V\right\rvert / \sqrt2\right\rceil$
  3. 以上述方法收缩出图 $G_1$
  4. 以上述方法收缩出图 $G_2$
  5. 递归计算 $G_1$ 和 $G_2$ 的答案
  6. 返回 $G_1$ 和 $G_2$ 中更优的那个

我们再来分析一下正确率。我们记 $p\left(n\right)$ 表示 $\left\lvert V\right\rvert = n$ 时，此算法的正确率。注意 $C$ 被全部保留的概率至少有 $1 / 2$。

$$ \begin{aligned} p\left(n\right) &\geq 1 - \left(1 - \frac12p\left(\left\lceil1 + \frac n{\sqrt2}\right\rceil\right)\right)^2 \\ &= \Omega\left(\frac1{\log n}\right) \end{aligned} $$

同时时间复杂度

$$ \begin{aligned} T\left(n\right) &= 2T\left(\left\lceil1 + \frac n{\sqrt2}\right\rceil\right) + O\left(n^2\right) \\ &= O\left(n^2 \log n\right) \end{aligned} $$

于是，现在的算法只需要 $\tilde O\left(n^2\right)$！

最大割

给定一个连通图 $G = \left(V, E\right)$。

把点分为两个点集 $S$ 和 $T$，满足 $S \cup T = V$ 且 $S \cap T = \varnothing$。

最大割就是要让 $S$ 和 $T$ 中的连边的边权和最大。

这是一个 NP 完全问题，我们尝试找一些多项式复杂度的近似解。

贪心算法

初始时，我们让 $S = T = \varnothing$，然后往里面加入点。

对于 $i = 1, 2, \ldots, n$，$V_i$ 加入 $S$ 或 $T$ 中的一个，以最大化当前的 $S$ 到 $T$ 的距离。

这样是 $0.5$ 近似的，证明毫无营养，不写。

Parity Search

其实达到 $0.5$ 近似是看起来比较容易的。因为如果让每个变量都随机地加入到 $S$ 或 $T$ 中，那么这个割的期望就是 $\left\lvert E\right\rvert / 2$。

我们稍微分析一下。假设用 $X = \left\{0, 1\right\}^n$ 来指示 $i$ 在 $S$ 中还是在 $T$ 中。

那么割的期望为

$$\mathbb E = \sum\limits_{\left(u, v\right) \in E} \Pr \left[X_u \neq X_v\right]$$

显然为 $\left\lvert E\right\rvert / 2$。

我们发现，如果我们有 $k = \left\lceil \log\left(n + 1\right)\right\rceil$ 个 $\left\{0, 1\right\}$ 随机变量 $Y$，那么我们其实是可以生成出 $n$ 个 相互独立 的随机变量的。

注意我们的要求是 相互独立，或者说 两两独立，因此通过这种方式生成的随机变量是符合要求的。

他们的期望是 $\left\lvert E\right\rvert / 2$，那么在所有方案中，至少有一个达到了 $\left\lvert E\right\rvert / 2$。

给出一个通过这 $k$ 个随机变量 $Y$，如何生成 $n$ 个 相互独立 的随机变量 $Z$。

先设 $S_1, \ldots, S_{2^k - 1}$ 表示 $\{1, 2, \ldots, k\}$ 的 $2^k - 1$ 个非空子集。

$$Z_i = \bigoplus\limits_{j \in S_i}X_j$$

这样，$SOL \geq \frac{\left\lvert E\right\rvert}2 \geq \frac{OPT}2$，也是 $0.5$ 近似！