团与最大团的搜索

· · 算法·理论

一个完全子图就叫团，最大团就是一个图中最大的完全子图。

相关问题通常是，定义一个团 C 的价值为 g(C)，让你求所有团价值的和 f(G) = \sum_{C\subseteq G} g(C)。这里的“和”不一定指数字的加法，也可以是 \max 等等。还需要定义一个乘法，对加法有分配率，且满足若 S\cup T 为团，则 g(S) \otimes g(T) = g(S\cup T)。举个例子，最大团问题就是定义 g(C) = |C|，然后定义加法为 \max，乘法为数字的加法。

基本的做法

最基础的方法是直接暴搜。枚举图的每一个子集，再 O(n) 判断是否是团。总复杂度 O(t(n)2^n)，t 是求出 g 的复杂度。

但是大多数最大团的题都是 n=40 的。过不了。

因此需要优化。通常来说，可以使用折半搜索。将点分成两个部分 A, B。对于 A 的每个子图 S，求出 f(S)。然后枚举 B 的每个子图 T，先检查其是否为团，然后查看其所有点邻居的交集 V，这样你可以得到一些全图上的团的信息 f(V\cap A) \otimes g(T)。容易发现这样恰好覆盖了原图所有的团。复杂度 O(t(n)2^{n/2}) + w(n)，t 是求出 g 的复杂度，w 是求出 f 的复杂度。比如求最大团时，可以高维前缀最大值，此时 w(n) = O(n2^{n/2})。

其实还可以 O(2^{n/2}) 算。具体来说，当要求 f(S) 时，枚举第一个 S 中的点 x，并记 x 相邻的点集为 P_x。可以发现 f(S)= f(S - \{x\}) \oplus f((S - \{x\})\cap P_x)。于是可以递推出 f。

更优秀的做法

以下的做法其实最劣复杂度都不低于 O(\text{poly}(n)2^{n/2})，但是在特殊情形下表现优异。

Bron-Kerbosch

这是一个深度优先搜索算法。似乎在最大团问题上进行优化后最劣复杂度是 O(\text{poly}(n)3^{n/3}) = O(\text{poly}(n)2^{0.528n}) 的，比上文做法略劣（不过可以计算得到，在 10^{10} 范围内这两个的理论差距都很小）。实验表明 BK 算法在很多情形下是很快的。真是玄学啊。

由于有点懒，而且 OI 不见得能用到，这里就直接放 gpt 翻译 wiki 的内容了。

团的一些性质

团其实有很多神奇的性质。这里是其中三个。

稀疏图上的枚举

当边数比较少的时候，根据上面的性质，点集可能枚举得冗余了。

我们枚举一个点 p，当它是它所属的团里面的、在原图中度数最小的点的时候，它有什么性质？

当它的度数不超过 \sqrt{2m} 时，它所属的团是容易枚举的——只需要枚举那些邻居就行了。而如果其度数大于 \sqrt{2m} 时，这个团中每个点度数都得大于 \sqrt{2m}。这些点的点数不应当超过 \sqrt{2m}，否则总边数将大于 m。

所以，只需要枚举 p 的邻居中度数大于等于 \deg(p) 的就行了。总复杂度 O(\text{poly}(n)2^{\sqrt{2m}})。比方说最大团问题可以 O(\sqrt m2^{\sqrt{2m}}) 算出。

其实这个思路和无向图枚举三元环的思路是一样的，就是对边定向云云。

那能不能在这个基础上折半搜索呢？显然是可以的。就是每次枚举一个点和邻居之后，对这个子图跑折半搜索即可。注意如果不可重复贡献（也就是要精确覆盖每一个团），那么枚举一个点后折半搜索应该强制要求这个点被选上。这样便不重不漏。

例题

CF1105E

P6571这个不怎么算吧

Yosupo

QOJ