1

给定一个无向图 G = G(V, E)，如何在多项式时间内找到其中最大团的大小？知道边的数量，我可以设置最大集团大小的上限

https://cs.stackexchange.com/questions/11360/size-of-maximum-clique-given-a-fixed-amount-of-edges

，然后我可以从该上限向下迭代到 1。由于这个上限是 O(sqrt(|E|))，我想我可以检查 O(sqrt(|E|) * sqrt 中的最大集团大小(|E|) * sqrt(|E|)) 时间。

有没有更有效的方法来解决这个 NP 完全问题？

4

2 回答 2

4

在图中找到最大的团是图的团数，也称为最大团问题（MCP）。这是图域中研究最深入的问题之一，并且已知是 NP-Hard，因此在一般情况下预计不会找到多项式时间算法来解决它（有特定的图配置确实具有多项式时间算法）。最大团甚至难以近似（即找到接近团数的数字）。

如果您对精确的 MCP 算法感兴趣，那么在过去十年中已经有了许多重要的改进，它们将性能提高了大约两个数量级。当前领先的算法系列是分支定界算法，并使用近似着色来计算界限。我列举了最重要的和改进之处：

  • 颜色分支 (MCQ)
  • 每个子问题中的静态初始排序（MCS 和 BBMC）
  • 重新着色：MCS
  • 使用位串对图形和主要操作进行编码 ( BBMC )
  • 减少到最大可满足性以改善界限（MaxSAT）
  • 选择性着色 (BBMCL)

和别的。它实际上是科学界非常活跃的研究方向。目前排名靠前的算法是 BBMC、MCS，我会说 MaxSAT。其中可能 BBMC 及其变体（使用位串编码）是当前领先的通用求解器。用于 BBMC 的位串库是公开的。

于 2014-07-22T15:01:08.393 回答
1

Well I was thinking a bit about some dynamic programming approach and maybe I figured something out.

First : find nodes with very low degree (can be done in O(n)). Test them, if they are part of any clique and then remove them. With a little "luck" you can crush graph into few separate components and then solve each one independently (which is much much faster). (To identify component, O(n) time is required).

Second : For each component, you can find if it makes sense to try to find any clique of given size. How? Lets say, you want to find clique of size 19. Then there has to exist at least 19 nodes with at least 19 degree. Otherwise, such clique cannot exist and you dont have to test it.

于 2014-03-31T00:41:29.110 回答