团与最大团的搜索

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

相关问题通常是，定义一个团 $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)\otimes g(\{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 的内容了。

团的一些性质

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

• 最大团等于补图的最大独立集。这个很容易证明。因此 $n$ 个点的图的最大团的最大数量是等于 $n$ 个点的图的最大独立集的最大数量的。

• $n$ 个点的图最大团最多有 $3^{n / 3}$ 个。BK 算法的复杂度与这个有关。有点难证，可以参考目前找到比较简短的证明，OEIS A000792。

• $m$ 条边的图，所有团大小都不超过 $\sqrt{2m}$。

  • 证明：大小为 $n$ 的团需要 $n^2/2$ 条边，所以团点数不超过 $\sqrt{2m}$。
  • 这个性质很简单，但是很有用：普通的算法可能枚举了过多的点集了，这些点集是没有用的。怎样减少枚举量呢？

稀疏图上的枚举

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

我们枚举一个点 $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