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

Question

我的问题

是否有一个有效的算法来找到最大权重(或最小权重)k- clique在一个完整的 k-partite 图中(根据 wikipedia，顶点相邻当且仅当它们属于不同的 partite 集时)？

有关条款的更多详细信息

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

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

我尝试过的

我在做项目的时候遇到过这个问题。由于我不是 CS 人员，所以我不确定复杂性等。

我在谷歌上搜索了几篇相关论文，但没有一篇涉及相同的问题。我还编写了一个贪心算法+模拟退火来处理(结果好像不太好)。我也尝试过动态编程之类的东西(但它似乎效率不高)。所以我想知道是否可以有效地计算出精确的最优值。提前致谢。

编辑 由于我的输入可能非常大(例如每个团中的顶点数为 2^k)，我希望找到一个非常快的算法(例如 k 的时间多项式)计算出最优结果。如果不可能，我们能否证明复杂性的某个下限？

Answer 1

广义最大团问题 (GMCP)

• 我了解到您正在寻找广义最大/最小团问题 (GMCP)，其中找到具有最大分数或最小成本的团是优化问题。
• 此问题是 NP-Hard 问题，如 Generalized network design problems 所示。 , 因此目前您的问题没有多项式时间精确解。
• 由于您的问题没有已知的多项式解，您有 2 个选择。缩小问题规模以找到确切的解决方案或通过放松问题找到估计的解决方案，这会引导您对最佳解决方案进行估计。

小问题规模的例子和解决方案

• 在小型 k 分图(在我们的例子中，k 为 30，每个分图有 92 个节点)中，我们能够通过繁重的分支定界算法在合理的时间内获得最优解。我们已将问题转换为另一个 NP 难问题(混合整数规划)，减少整数变量的数量，并使用 IBM Cplex 优化器找到 GMCP 的最优解。
• 您可以找到我们的 project page和纸很有用。我也可以与您分享代码。

如何估算解决方案

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

更一般的问题(Generalized Maximum Multi Clique Problem)

• 在另一项工作中，我们解决了广义最大多派系问题 (GMMCP)，其中感兴趣的是在完整的 k 部分图中最大化分数或最小化选择多个 k 派系的成本。您可以找到 project page通过搜索 GMMCP 跟踪。