问题描述
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声称,对于图形的大小,整数求解器可以做得很好(并产生更好的结果)