9

我的问题

是否有一种有效的算法可以在完整的k分图中找到最大权重（或最小权重）k-团（根据维基百科，当且仅当它们属于不同的分集时，顶点相邻的图）？

有关条款的更多详细信息

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

请注意，clique 的大小是 k，它是完整 k-partite 图中可能的最大 clique 大小。

我试过的

我在一个项目中遇到了这个问题。由于我不是 CS 人员，因此我不确定复杂性等。

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

编辑由于我的输入可能非常大（例如，每个团中的顶点数是 2^k），我希望找到一个非常快速的算法（例如 k 的多项式）来计算出最佳结果。如果不可能，我们可以证明复杂性的一些下限吗？

4

2 回答 2

5

广义最大团问题 (GMCP)

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

小问题的示例和解决方案

  • 在小的 k-partite 图中（在我们的例子中 k 是 30，每个partite 有 92 个节点），我们能够通过繁重的分支和边界算法在合理的时间内获得最优解。我们已经将问题转化为另一个 NP-hard 问题（混合整数规划），减少整数变量的数量，并使用 IBM Cplex 优化器找到 GMCP 的最优解。
  • 您会发现我们的项目页面和论文很有用。我也可以和你分享代码。

如何估计解决方案

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

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

  • 在另一项工作中，我们解决了广义最大多团问题 (GMMCP)，其中最大化分数或最小化在完整 k 部图中选择多个 k 团的成本是有意义的。您可以通过搜索 GMMCP Tracking找到项目页面。
于 2016-03-01T04:11:01.183 回答
3

加权图中的最大团问题通常是棘手的。在您的情况下，如果图形包含 N 个节点，您可以在 N ** k 时间内枚举所有可能的 k-cliques。如果 k 是固定的（不知道是否是），那么您的问题是简单的多项式可解决的，因为这是 N 中的多项式。如果 k 是自由参数，我不相信这个问题是易于处理的，因为我不能看看 k-partite 图的假设如何使问题比一般问题简单得多。

您的问题在实践中的难度还取决于权重的分布方式。如果所有的权重都非常接近，即“最好”和“好”之间的差异比较小，那么问​​题就很难了。如果边缘的权重差异很大，问题可能会更容易，因为贪心算法可以为您提供一个好的“初始”解决方案，您可以使用该解决方案和后续好的解决方案来限制您使用众所周知的分支的组合搜索绑定方法。

于 2013-06-18T12:53:31.937 回答