团与最大团的搜索

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

相关问题通常是，定义一个团 $C$ 的价值为 $g(C)$，让你求所有团价值的积 $f(G) = \prod_{C\subseteq G} g(C)$。这里的“积”不一定指数字的乘法，也可以是 $\max$、加法等等。举个例子，最大团问题就是定义 $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\cup A) * g(T)$。容易发现这样恰好覆盖了原图所有的团。复杂度 $O(t(n)2^{n/2}) + w(n)$，$t$ 是求出 $g$ 的复杂度，$w$ 是求出 $f$ 的复杂度。比如求最大团时，需要高维前缀最大值，此时 $w(n) = O(n2^{n/2})$。

更优秀的做法

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

Bron-Kerbosch

这是一个深度优先搜索算法。可以证明在最大团问题上进行优化后最劣复杂度是 $O(\text{poly}(n)3^{n/3}) = O(\text{poly}(n)2^{0.528n})$ 的，比上文做法略劣（不过可以计算得到，在 1e10 范围内这两个的理论差距都很小）。实验表明 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}})$。

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

那能不能在这个基础上折半搜索呢？显然是可以的。将图定向后，枚举图中的每个点 $p$，对 $p$ 以及 $p$ 的出边构成的集合跑一下上文的折半搜索即可。正好，由于定了向，只要钦定 $p$ 在这个集合里面一定被选，这样枚举出来的团不重不漏。因此应当重新定义 $f(p, S)$，表示 $S$ 所有包含 $p$ 的团的价值的积。

例题

CF1105E

P6571这个不怎么算吧

Yosupo