algorithm - 图的团数

Question

我想知道一种快速算法，只找到大约 100 个顶点的图的团数（实际上没有找到团）。

我正在尝试解决以下问题。 http://uva.onlinejudge.org/external/1/193.html

Answer 1

这是 NP 完全的，你不能比实际找到最大团并计算它的顶点更好。来自维基百科：

集团问题包括：

• 解决测试图是否包含大于 N 的团的决策问题

这些问题都很困难：集团决策问题是完全NP的（卡普的 21 个NP完全问题之一），

如果您可以在 中找到团数P，则决策问题在 中是可回答的P（您只需计算团数并将其与 进行比较N）。

既然决策问题是NP-Complete，求一般图的团数必然是NP-Hard。

Answer 2

尽管问题是 NP 难题，但您提到的图形大小对于当今最快的最大团精确求解器（对于任何配置）来说都不是问题。

如果您准备好实现代码，那么我建议您阅读与算法系列 MCQ、MCR 和 MCS 以及系列 BBMC、BBMCL 和 BBMCX 相关的论文。一个有趣的起点是 Prosser [Prosser 12]的比较调查。它包括对这些算法的 Java 实现的解释。

Answer 3

正如其他人已经说过的，这可能真的很难。

但就像许多理论上的难题一样，如果有好的算法和合适的数据，它在实践中可能会很快。如果你实现了类似 Bron-Kerbosch 的方法来寻找派系，同时跟踪你迄今为止找到的最大派系大小，那么你可以回溯到没有结果的搜索树。

例如，如果您发现其中有 20 个节点的团，并且您的网络中有大量度数小于 20 的节点，您可以立即将这些节点排除在进一步考虑之外。另一方面，如果度数分布更均匀，那么这可能与找到所有派系一样慢。