最大团 / 最大独立集问题

· · 算法·理论

前置知识与记号

独立集：无向图 G=(V,E) 中 V 的一个子集 S，使得 \forall u,v\in V,(u,v)\neq E，即 S 中任意两点之间都没有连边；团则正好相反，要求 S 中任意两点之间都有连边。

给定一个无向图 G=(V,E)，求它的最大独立集（或最大团，复杂度和边数没有关系时等价），这是知名的 NP-Complete 问题。

:::info[最大独立集问题是 NP-Complete 的证明]{open} 考虑将 3-SAT 归约到最大独立集问题。

现有变量集 X=\{x_1,x_2,\cdots\!,x_n\}，对于实例 C=C_1\land C_2\land\cdots\land C_m 的每个子句 C_i=x_{i,1}\vee x_{i,2}\vee x_{i,3}，在图 G=(V,E) 中创建三个节点 v_{i,1},v_{i,2},v_{i,3}，在它们两两之间连边；同时对于两个不同子句中出现的变量 x_i 和 \neg x_i，在它们对应的节点之间连边。

不难验证，3-SAT 问题有解当且仅当 G 有大小为 m 的独立集——由抽屉原理可知，这也是可能的最大独立集。 :::

在一些特殊的图上（譬如树、仙人掌，乃至广义串并联图），存在能够在多项式复杂度内求解最大独立集的算法，但这不是本文讨论的主要内容，只提一嘴，想看的可以展开下面的框框 OwO。

:::success[我是折叠框 QwQ] 树：没有上司的舞会，树形 DP，设 f_{u,0/1} 表示 u 子树内 u 不选 / 选的最大独立集，容易转移，时间复杂度为 \mathcal O(n)。

仙人掌：无归岛，可以使用圆方树，这里讲一个不用圆方树的做法：先求出 DFS 树，设 f_{u,0/1,0/1} 表示 u 子树内，u 不选 / 选，u 所在（u 不为链顶）环的环底不选 / 选的最大独立集，转移分讨 (u,v) 是树边还是返祖边，以及 u 是不是 v 所在环的环顶即可。

广义串并联图：对于每个点簇（Rake 时并入的那个点）u 记录 a_{u,0/1} 表示 u 不选 / 选时 u 所代表的簇的最大独立集，对于每个边簇 e 记录 f_{e,0/1,0/1} 表示 e 的两个界点分别不选 / 选时的最大独立集，不计入界点的贡献，不难合并。 :::

记 N(u) 表示所有与 u 相连的点组成的集合，即 N(u)=\{v\in V\mid(u,v)\in E\}，记 N[u]=N(u)\cup\{u\}。

记号 Soft-O：记 \widetilde{\mathcal O}(f(n))=\mathcal O(f(n)\operatorname{polylog}f(n))。在这篇文章中，这意味着我们很多时候只需要关心时间复杂度 \widetilde{\mathcal O}(c^n) 中的底数 c，这也是影响大规模数据下时间效率的最重要的因素。

朴实无华的暴力与胃酸

最朴素的暴力是，枚举 V 的每个子集 S\subseteq V 然后判断其是否为独立集，时间复杂度为 \widetilde{\mathcal O}(2^n)，具体地说，每次直接重新判断是 \mathcal O(n2^n) 的，但可以通过将 u 的邻接点集 N(u) 压成二进制数，然后和当前点集 S 求交快速得到 S\cup\{u\} 内部的边数，这样复杂度就是 \mathcal O(2^n) 的。

另外还有一些神秘的随机化算法，比如说按照随机顺序打乱很多遍然后每次依次贪心地尝试加入节点之类的，在随机数据下表现良好，但也容易构造数据 hack 掉，并且无法求出团个数等需要计数的信息。

我们可能会想，既然最大独立集是 NP-Complete 的，那能不能设计一个多项式时间复杂度的近似算法，使得存在常数 c\in(0,1)，其给出的答案均不小于正解的 c 倍呢？很遗憾也是不行的，事实上，除非 \textsf{P}=\textsf{NP}，否则不存在多项式复杂度的算法能以常数倍近似计算该问题。

不过在一些特殊图上面这倒可行，如果我没看错的话，这里还有一篇多项式复杂度内近似求解平面图最大独立集的论文？反正以我的水平肯定看不懂就是了咔。

第一次进步

考虑类似折半搜索的做法，先取反图转化为求最大团，将 V 均分为两个点集 L,R，在 \mathcal O(2^{n/2}) 的时间复杂度内预处理出 L 和 R 内的每个团，然后考虑如何合并两个团 C_L\subseteq L 和 C_R\subseteq R，发现能够合并的充要条件是 C_R\subseteq\bigcap\limits_{u\in L}N(u)，可以通过 SoS DP（即常说的高维前缀和）预处理出满足 C_R\subseteq S 的 C_R 中 |C_R| 的最大值，于是复杂度为 \mathcal O(n2^{n/2})，平衡一下可以做到 \mathcal O(\sqrt{n}2^{n/2})，还不够优秀。

考虑到瓶颈在于 SoS DP，考虑类似上面的方式，设被 S 包含的最大团大小为 f_S，对于 S 中的任意一个点 u，分类讨论 u 是否在一个团中，有：

f_S=\max(f_{S\setminus\{u\}},f_{S\cap N(u)}+1)

这样时间复杂度就为严格的 \mathcal O(2^{n/2})，底数为 \sqrt2\approx1.4142。

有一个可能更好写的相同复杂度的做法：考虑记忆化搜索，当然直接全记下来肯定不行，如果当前集合 S\subseteq\left\{1,2,\cdots\!,\left\lfloor\dfrac n2\right\rfloor\right\} 就记下来，然后像上面那样，取编号最大的点 u，去搜索 S\setminus\{u\} 和 S\cap N(u)，前 \left\lceil\dfrac n2\right\rceil 步会产生 \mathcal O(2^{n/2}) 个状态，后 \left\lfloor\dfrac n2\right\rfloor 步由于记忆化，每个状态只会搜一次，因此复杂度为 \mathcal O(2^{n/2})。

搜索的绝对力量 Ⅰ——Bron-Kerbosch 算法

注意到极大团个数似乎不会很多，把点集 V 均分成三部分 A,B,C，不同部分的点两两之间连边，这样有 \mathcal O(3^{n/3}) 个极大团，下面证明这个量级就是上界，更具体地说，设 n 个点的图 G 至多有 F_n 个极大团，那么有：

F_n=\left\{ \begin{aligned} &3^{n/3}&\operatorname{if} n\equiv0\pmod 3\\ &4\cdot3^{(n-4)/3}&\operatorname{if} n\equiv1\pmod 3\\ &2\cdot3^{(n-2)/3}&\operatorname{if} n\equiv2\pmod 3 \end{aligned} \right.

:::info[证明]{open} 先把团转成独立集。考虑对 n 使用数学归纳法，n\le 3 的情况容易验证，下面假定 n\ge 4。对于 n 个点的图 G=(V,E)，设 G 中极大独立集个数为 f(G)，若 G 是一个完全图或零图则结论显然成立，否则设 v 是 G 中度数最小的点，\deg_v=d，有 N[v]\subsetneq V。

对于极大独立集 S，一定有 S\cap N[v]\neq\varnothing，否则 S\cup\{v\} 是一个更大的独立集。进一步地，对于 w\in S\cap N[v]，S\setminus\{w\} 是点集 V\setminus N[w] 中的极大独立集，因此有：

f(G)\le\sum_{w\in N[v]}f(V\setminus N[w])

由于 \deg_w\ge d，有 f(G)\le(d+1)F_{n-d-1}。注意 4\cdot 3^{(n-4)/3}\le F_n\le 3^{n/3}，分讨 d 和 n 的以下取值情况：

对于 d=1 的情况，再分 n 模 3 的余数讨论：

故有 f(G)\le F_n，考虑构造：

  3. n\equiv 2\pmod 3$，放一条单独的边和 $\dfrac{n-2}3$ 个三元环即可。$\square

    ::: 既然如此，能不能设计一个搜索算法，使得每个极大团恰好被遍历一遍，这样复杂度就是 \widetilde{\mathcal O}(3^{n/3})\approx\widetilde{\mathcal O}(1.4422^n) 的呢？欸，还真可以。

一个简单的想法是，DFS 时记录两个点集，R——当前团内的点，以及 P——目前可选的点，也就是 \bigcap\limits_{u\in R}N(u)，初始时 R=\varnothing，P=V，伪代码如下：

DFS(R, P):
    if P = ∅:
        return R as a maximal clique
    for v ∈ P:
        DFS(R ∪ {v}, P ∩ N(v))

然而手玩一下就会发现，对于三元环 \{1,2,3\}，团 \{1,2,3\} 被以 1,2,3 为起点分别都遍历了一次，为了避免这种重复遍历情况，我们加入一个集合 X，其记录着所有和 R 中所有点都相连且作为过 DFS 的起点的点，伪代码如下：

DFS(R, P, X):
    if P = ∅ ∧ X = ∅:
        return R as a maximal clique
    for v ∈ P:
        DFS(R ∪ {v}, P ∩ N(v), X ∩ N(v))
        P = P \ {v}
        X = X ∪ {v}

仍然以三元环 \{1,2,3\} 为例，选择 1 作为起点，处理完 1 的递归分支后有 P=\{2,3\}，X=\{1\}，之后选择 2 作为起点时，可能会找到团 \{2,3\}，但不会找到 \{1,2,3\}，因为 1 此时已经在 X 中了，不会再重复加入到 R 中；而在找到 \{2,3\} 时，虽然 P=\varnothing，但此时 X=\{1\}，所以当前 R 不是“新发现”的极大团，而是某个更大的、先前已经发现过的团 R\cup X 的子集。

因此，每个极大团至多被搜索到一次，递归深度为 n，时间复杂度为 \widetilde{\mathcal O}(3^{n/3})\approx\widetilde{\mathcal O}(1.4422^n)。虽然复杂度不如 \mathcal O(2^{n/2}) 优秀，但是该算法能够直接得出图 G 中的所有极大团，在某些情况下可能有优势？

搜索的绝对力量 Ⅱ……以及 The Measure & Conquer Method

而目前 OI 中最常用的是以下搜索算法：对于点集 S，找出 S 的导出子图中度数最大的点 u，若 \deg_u\le 2 说明 S 由若干个环和链构成，可以直接 \mathcal O(n) 算出 S 的最大独立集；否则递归 S\setminus\{u\} 和 S\setminus N[u]。

那么这个看似暴力的东西复杂度怎么样呢？列出式子 T(n)=T(n-1)+T(n-4)，由此得 c^4=c^3+1，解得 c\approx1.3803，也就是说复杂度约为 \widetilde{\mathcal O}(1.3803^n)，而且几乎跑不满，和上面的做法相比有较大的优势。

Q：为什么只有实数根影响量级？
A：只是恰好实根的模长最大？

能不能更给力一点？在上面的算法中再加上一个剪枝：如果 S 中存在一个度数 \le1 的点，显然可以贪心地选择它然后直接递归 S\setminus N[u]，这对复杂度有什么影响？

这就不得不提到一个分析复杂度的方法：The Measure & Conquer Method，有人管它叫“测量治之”，简单地说，平时分析复杂度时，T(n) 中的 n 都是点数之类的东西，每个对象都是平等的；而现在我们给每个对象带上一个权值，类似平衡规划的思想，将 G 的总权值记为 W(G)，通过对 T(w) 的重新分析，有时会导出更优的时间复杂度。

以上述算法为例，下面的分析均忽略复杂度中的 \operatorname{poly} n 因子。由于度数 \le1 的点会被立即从 S 中除去，将其赋值为 0；而度数为 2 的点不会立即被除去，而是等到度数至少为 3 的点被处理干净之后再在均摊 \mathcal O(1) 的时间复杂度内被除去，看起来其贡献比度数至少为 3 的点要小，令度数至少为 3 的点的权值为 1，不妨先设度数为 2 的点的权值为 \dfrac12。

执行分枝时，每个点的度数至少为 2，且至少有一个度数为 3 的点。如果图中所有点的度数均 \le3，这时我们选择了度数为 3 的点 u，对于第一种情况（不将 u 加入独立集），W(S) 首先会减少 u 的权值 1，同时对于 v\in N(u)，若 \deg_v=3，那么它会下坠到 \deg_v=2，其权值从 1 减少至 \dfrac12；否则 \deg_v=2，它会下坠到 \deg_v=1，其权值从 \dfrac12 减少到 0；总而言之，这种情况下 W(S) 会减少 \dfrac25；对于第二种情况（将 u 加入独立集），包含 u 在内的所有点都会从 S 中被除去，这时 W(S) 也会至少减少 \dfrac25，因此有 T(w)=2T\left(w-\dfrac25\right)，解得 T(w)\approx\widetilde{\mathcal O}(1.3195^n)。

还别急，还有一种情况：存在一个度数 \ge4 的点，这时候下坠的权值就不一定有 \dfrac32 了，因此不能套用上面的分析。不过这时最坏的情况也就是每次分枝的点度数至少为 4 了，然后就会回到上面的情况，这时有 T(n)=T(n-1)+T(n-5)，即 c^5=c^4+1，解得 c\approx1.3248。由于 1.3195<1.3248，那么该算法的总复杂度约为 \widetilde{\mathcal O}(1.3248^n)。

令人疑惑的是，我之前似乎没有看到有人在 OI 中引进这个分析方法并得出这个复杂度？可能是这个东西没有什么实践上的作用，或者是我孤陋寡闻了吧 OwO。

upd：这个剪枝似乎不会使得运行速度更快：对于一条链，DFS 会一直进行到把这条链删完为止；而没有剪枝的代码反而会把这条链留到所有点度数都 \le2 再整个处理，递归深度和常数可能会更小？

这是……什么？

小小偏一下题，这里介绍一个 \widetilde{\mathcal O}(1.2852^n) 但感觉常数可能会起飞的搜索算法，来自这篇论文，建议边看边画一下图帮助理解咔。

仍然像上面那样，如果 S 的导出子图中有度数 \le1 的点则直接选择；否则如果所有点度数都 \le2 就直接算，下面考虑每个点的度数至少为 2，且至少有一个度数为 3 的点的情况。

如果存在度数为 2 的点，那么就一定存在一个度数为 2 的点 v，设 N(v)=\{w_1,w_2\}，使得 \deg_{w_1}\ge 3 或 \deg_{w_2}\ge 3。若 (w_1,w_2)\in E，不难发现直接选择 v 一定不劣，递归到 S\setminus N[v] 求解；否则分讨选择 v 还是同时选择 w_1,w_2，递归到 S\setminus N[v] 和 S\setminus(N[w_1]\cup N[w_2]) 分别求解。

否则每个点度数都不小于 3，如果存在度数为 3 的点，譬如点 v，设 N(v)=\{w_1,w_2,w_3\}。如果它们仨两两之间均有边，同上不难发现直接选 v 一定不劣，递归到 S\setminus N[v] 求解；否则如果它们仨之间有两条边，不妨设为 (w_1,w_2) 和 (w_1,w_3)，大概长一个燕尾的形状，将所有点按照邻边分类，可以发现选择 w_1 一定不优于选 v，因此分讨选 v 还是选 w_2,w_3，递归到 S\setminus N[v] 和 S\setminus(N[w_2]\cup N[w_3]) 分别求解。

否则如果它们仨之间只有一条边，不妨设为 (w_1,w_2)，那么分三种情况：选择 v，选择 w_1,w_3 和选择 w_2,w_3，递归到 S\setminus N[v]、S\setminus(N[w_1]\cup N[w_3]) 和 S\setminus(N[w_2]\cup N[w_3]) 分别求解；否则它们互不相连，分五种情况：选择 v，选择 w_1,w_2,w_3，选择 w_1,w_2，选择 w_1,w_3，选择 w_2,w_3，剩下的一定不优。但是你发现真的直接这样递归下去就炸了，而且会有重复遍历到的 S，因此把第二种情况包含到后面随便一个情况（比如说第三种情况）里，递归到 S\setminus N[v]、S\setminus(N[w_1]\cup N[w_2])、S\setminus(N[w_1]\cup N[w_3]\cup\{w_2\}) 和 S\setminus(N[w_2]\cup N[w_3]\cup\{w_1\}) 分别求解，这里多减去的一个点大概起 BK 算法中 X 集合的作用。

否则每个点的度数都 \ge 4，如果存在一个点 v 的度数 \ge 5，就直接递归到 S\setminus N[v] 和 S\setminus\{v\} 分别求解；否则每个点度数都为 4，操作一次就会回到上面的情况。

考虑对每个分枝分析复杂度：

  1. 对于 \deg_v=2，若 (w_1,w_2)\not\in E，此时有 T(n)=T(n-3)+T(n-5)，解得 c\approx1.1939；
  2. 对于 \deg_v=3，两条边的情况有 T(n)=T(n-4)+T(n-6)，解得 c\approx1.1510；一条边的情况有 T(n)=T(n-4)+2T(n-6)，解得 c\approx1.2334；没有边的情况有 T(n)=T(n-4)+T(n-6)+2T(n-7)，解得 c\approx1.2696；
  3. 对于 \deg_v\ge 5 的情况，有 T(n)=T(n-1)+T(n-6)，解得 c\approx1.2852。

综上所述，该算法的时间复杂度为 \widetilde{\mathcal O}(1.2852^n)。

我也不知道为啥我有些和原论文算出来的不一样，我这个好像是对的（？）

等我哪天写个代码试试，跑路了。

……更进一步？

这篇论文给出了一个 \widetilde{\mathcal O}(1.2201^n) 的算法，等我哪天有空了系统地学习了 The Measure & Conquer Method 再来吧，咕咕咕。