求任意图的最大权独立集的启发式算法 [英] Heuristic to find the maximum weight independent set in an arbritary graph

问题描述

MWIS(最大权重独立集)是一个NP-完全问题，因此如果P！=NP，我们无法在足够好的时间复杂度内找到解决方案。

我正在寻找一种算法，可以在一个良好的时间复杂性内在任意图形中找到MWIS的近似值。我当前正在处理一个具有128个节点和3051条边的连通图。

我找到了this paper，但它似乎只适用于具有唯一MWIS的二部图。

如果有人能帮我一些参考，或者更好的工作算法的伪代码，我将非常高兴。

推荐答案

可以将其表述为以下问题。假设图中的每个顶点v都有权w(V)。您定义了一个变量x(V)，并使用一些开箱即用的线性规划解算器来求解

max sum_v w(V)x(V)(最大化所选顶点的权重)

受制于

中x(U)+x(V)<；=1，(u，v)(不带邻居)

和

{0，1}中的x(V)(只能选择取或不取顶点)

---

这是一个组合问题(最后一个约束是顶点数的指数)。有两种方法可以从此处继续：

• 将最后一个约束切换为

  x(V)in[0，1](选择顶点的范围)

  使用LP求解器求解，然后继续this paper, 4.3。

• 在下面的评论中，David Eisenstat声称，对于图形的大小，整数求解器可以做得很好(并产生更好的结果)

这篇关于求任意图的最大权独立集的启发式算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！