高级算法之最小割和最大割

最小割和最大割

1 最小割

1.1 Karger’s Contraction algorithm

Contraction操作: $Contract(G, uv)$表示将图G中点u和v合并, uv之间的边删除

RandomContract算法

RandomContract算法:

while |V| > 2 do

  • 随机选择边$uv\in E$
  • $G=Contract(G, uv)$

return $C=E$

复杂度: 运行$n-2$次Contract, 每次Contract为$O(n)$, RandomContract为$O(n^2)$

1.2 Analysis of accuracy

引理
对于任意一个特定最小割C,

证明要点:

  • C为G的最小割, $e\not\in C$, 则C是$G’=Contract(G,e)$的最小割

    • 因为G’中的割都是G中的割, 且C在G’中”存活”, 所以C是G’的最小割
  • C被RandomContract返回当且仅当对于任意$i=1,2,…,n-2, e_i\not\in C$

  • 根据链法则, $p_C$转化为$\Pi_{i=1}^n Pr[e_i\not\in C|\forall j < i, e_j\not\in C]$

  • 证明$|E|\ge \frac{|V||C|}{2}$
    • (多重)图中的最小度一定大于等于最小割$|C|$, 因为最小度条边一定能构成一个割
    • $2|E|=\sum_v d_v\ge |V|\cdot d_\min\ge |V|\cdot|C|$
  • $p_i=1-\frac{|C|}{|E_i|}\ge 1-\frac{2}{V_i}=1-\frac{2}{n-i+1}$

  • 运行RandomContract算法$t=\frac{n(n-1)\ln n}{2}$次, 返回最小的那个, 就可以达到$1-\frac{1}{n}$的准确率, 称为with high probability

  • 总复杂度$O(n^4\log n)$

1.3 A Corollary by the Probabilistic Method

推论
对于n度图G, 不同的割的数量最多为$n(n−1)/2$
  • 证明: $1\ge p_{correct}=\sum_{C\in \mathcal C}p_c\ge |\mathcal C|\frac{2}{n(n-1)}$

1.4 Fast Min-Cut

  • 改进方向: 因为$\Pr[e_1,\cdots,e_{n-t}\not\in C]\ge\prod_{i=1}^{n-t}\frac{t(t-1)}{n(n-1)}$, 只有当$t$很小的时候才概率才低.
  • 改进思路: 先将顶点数Contract到一个相对小的值, 利用递归找到更小的那个割
  • 改进方法:
    • 将RandomContract中的终止条件$|V|\ge 2$改为$|V|\ge t$, 后面发现$t=\lceil1+n/\sqrt 2 \rceil$较合适
    • FastCut(G):
      • if $|V|\le 6$穷举得到最小割
      • else
        • G1 = RandomContract(G, t)
        • G2 = RandomContract(G, t)
        • 返回FastCut(G1)和FastCut(G2)中较小的那个
  • 根据上面的式子, 易证RandomContract后最小割大小不变的概率大于等于1/2
  • FastCut返回的不是最小割的概率:
    • 根据归纳法为$\Omega(1/\log n)$, 具体过程略
  • 一次FastCut时间复杂度$O(n^2\log n)$
  • 运行FastCut算法$O((\log n)^2)$次, 准确率达到$1-O(1/n)$, 总复杂度$O(n^2\log^3 n)$

2 最大割

  • NPC

2.1 Greedy algorithm

贪心算法:

  • 初始$S=T=\emptyset$
  • for i = 1, 2, …, n

    • $v_i$加入S或者T, 以最大化当前的$|E(S, T)|$
  • 多项式时间

近似度分析

  • $OPT_G$上界为|E|
  • 引理1: $|E|=\sum_{i=1}^n(|E(S_i, \{v_i\})| + |E(T_i, \{v_i\}|)$
    • 可以理解为每条边遍历一次
  • 引理2: $SOL_G=\sum_{i=1}^n max(|E(S_i, \{v_i\})| , |E(T_i, \{v_i\}|)$
    • 理解为每次选择和S或T相连的边较多的
  • 因此$SOL_G\ge \frac{1}{2}OPT_G$
  • 近似比为0.5

2.2 Derandomazation by conditional expectation

  • 随机割:

    • 用$X_v$为0或1表示$v$属于S还是T
    • $\mathbb E[|E(S,T)|]=\sum_{uv\in E}\mathbb E[I[X_u\neq X_v]] = \frac{|E|}{2}\ge \frac{OPT_G}{2}$
    • 因此至少有一组分割满足$E(S,T)\ge\frac{OPT_G}{2}$
  • 条件概率去除随机化:

    • 可以作一棵决策树, 第i层表示$v_i$的选择

    • 对于$x_{v_1}$, 因为$\mathbb E[E(S, T)]=\frac{1}{2}\mathbb E[E(S, T)|x_{v_1}=0]+\frac{1}{2}\mathbb E[E(S, T)|x_{v_1}=1]$, 所以存在$x_1\in\{0,1\}$, 满足$\mathbb E[E(S, T)|x_{v_1}=x_1]\ge \mathbb E[E(S,T)]$

    • 同理存在一系列$x_i$满足

    • 综上存在$x_1, x_2, …, x_n$的01序列使得$\mathbb E[E(S, T)|x_{v_1}=x_1, x_{v_2}=x_2, …, x_{v_n}=x_n]\ge \mathbb E[E(S, T)|]$

  • 也就是存在$\hat S, \hat T$满足$\mathbb E[\hat S, \hat T]\ge \frac{OPT_G}{2}$

算法

  • 初始$S=T=\emptyset$
  • for i = 1, 2, …, n
    • $v_i$选择加入S或T, 满足在前面选择的基础上最大化割的均值, 也就是使得$\mathbb E[E(S,T)|x_{v_1}=x_1, x_{v_2}=x_2, …, x_{v_{i}}=x_{i}]$最大 (计算该期望只需要计算还没完全确定的边)
  • 实际上算法和上面的贪心完全一致

2.3 Derandomazation by pairwise independence

  • 注意上面算法实际上只要求成对独立, 因此可以优化

  • 用$Y_v$表示v属于S还是T

  • 定理:

    • 01随机变量$X_1, X_2, …, X_k$
    • $S_1, S_2, …, S_{2^k-1}\subseteq \{1,2,…,k\}$为$\{1,2,…,k\}$的非空子集的枚举
    • 对任意i, $Y_i=\oplus_{j\in S_i} X_j$
    • $Y_1, Y_2,…,Y_{2^k-1}$就是成对独立均匀随机位
  • 如果$Y_v$是按照上面方式构造, $k=\lceil\log(n+1)\rceil$

    有$\mathbb E[|E(S,T)|]=\sum_{uv\in E} Pr[Y_u\neq Y_v=|E|/2$

  • 因此存在S, T满足$|E(S,T)|\ge |E|/2\ge OPT/2$

  • 搜索空间降低为$2^k-1=O(n^2)$

算法

  • $k=\lceil\log(n+1)\rceil$
  • 对所有$\vec x\in \{0,1\}^k$
    • 初始$S_{\vec x}=T_{\vec x}=\emptyset$
    • for i = 1, 2, …, n
      • if $\oplus_{j: \lfloor i/2^j\rfloor \mod 2 = 1} x_j=1$(即i二进制下为1的位都异或起来), $v_i$加入$S_{\vec x}$
      • else $v_i$加入$T_{\vec x}$
  • 返回$\{S_{\vec x}, T_{\vec x}\}$有最大$|E(S_{\vec x}, T_{\vec x})|$

算法分析

  • 该算法的实质是遍历解空间, 但是解空间比之前小得多
  • 近似比也是1/2