完全 k-部图中的最大权重 k-团

Question

我的问题

是否有一种有效的算法来找到完全k-部分图中的最大权重（或最小权重）k-团（如果且仅当它们根据wikipedia属于不同的部分集时，顶点才相邻）？

有关术语的更多细节

最大权重团：图中的每条边都有一个权重。团的权重是团中所有边的权重之和。目标是找到具有最大权重的团。

请注意，团的大小为k，这是完全k-部分图中可能的最大团大小。

我尝试过的方法

我在项目中遇到了这个问题。由于我不是计算机科学专业人员，所以对复杂度等方面不确定。

我已经谷歌了几篇相关论文，但没有一篇涉及相同的问题。我还编写了一个贪心算法+模拟退火来处理它（结果似乎不好）。我也尝试过类似动态规划的东西（但似乎不太有效）。所以我想知道是否能够高效地计算出确切的最优解。提前致谢。

编辑：由于我的输入可能非常大（例如每个团中的顶点数为2^k），我希望找到一个真正快速的算法（例如k的多项式时间）来处理最优结果。如果不可能，我们能证明复杂度的某些下限吗？

- linusz

---

什么是权重？ - Colonel Panic

@ColonelPanic 图中的每条边都有一个权重。团的权重是团中所有边的权重之和。 - linusz

没事，我忘了刚才的评论，我错读了你的文字并已删除了我的错误评论 :) - Regenschein

@fordprefect 无论如何，感谢您的关注 :) - linusz

这可能对您有用 - http://www.engineering.uiowa.edu/~krokhmal/pdf/bitCLQ.pdf - Bill

Answer 1

广义最大团问题（GMCP）

• 我理解您正在寻找广义最大/最小团问题（GMCP），其中寻找具有最大分数或最小成本的团是优化问题。
• 如广义网络设计问题所示，这个问题是一个NP难问题，因此目前没有多项式时间的确切解决方案。
• 由于没有已知的多项式解决方案，您有两个选择。通过减少问题规模来找到精确解决方案，或通过放宽问题来找到估计解决方案，并导致对最佳解决方案的估计。

小问题大小的示例和解决方案

• 在小的k部图中（在我们的情况下，k为30，每个部分都有92个节点），我们能够通过重量级分支和限制算法在合理的时间内获得最优解。我们将问题转换为另一个NP难问题（混合整数规划），减少了整数变量的数量，并使用IBM Cplex优化器找到了GMCP的最优解。
• 您可以在我们的项目页面和论文中找到有用的信息。我也可以与您分享代码。

如何估计解决方案

• 这个NP难问题的一个直接估计方法是放松混合整数规划问题，并将其作为线性规划问题解决。当然，它会给你一个解决方案的估计，但在实践中仍然可能得到一个合理的答案。

更一般的问题（广义最大多团问题）

• 在另一项工作中，我们解决了广义最大多团问题（GMMCP），其中在完全的k部图中选择多个k-团的最大分数或最小成本是感兴趣的。您可以通过搜索GMMCP跟踪来找到项目页面。

- Shayan Modiri

---

项目页面已经出现了403错误。不过，我认为我成功找到了引用的论文链接： https://doi.org/10.1109/CVPR.2015.7299036 - Sirko

Answer 2

在加权图中，最大团问题通常是不可解的。在您的情况下，如果图包含N个节点，则可以在N ** k时间内枚举所有可能的k-团。如果k是固定的（不知道是否是），则您的问题很容易在多项式时间内解决，因为这是N的多项式。如果k是自由参数，则我认为该问题不能被解决，因为我无法看到假设k-部分图会使问题从一般问题中显着简化。

实际上，您的问题有多难取决于权重分布如何。如果所有权重非常接近，即“最佳”和“好”的差异相对较小，则问题非常困难。如果边缘上的权重差异很大，则问题可能更容易，因为贪心算法可以给您一个良好的“初始”解，并且您可以使用该解和随后的良好解来使用众所周知的分支限界方法来限制组合搜索。

- Antti Huima

---

谢谢。如果k是固定的，您认为是否有更好的算法（例如NlogN算法）来解决这个问题，因为我的N可能非常大（例如2^k）？ - linusz

不，我并不这么认为。这是一个困难的问题。 - Antti Huima