求任意图的最大权独立集的启发式算法

人气:634 发布:2022-10-16 标签: algorithm graph linear-programming graph-algorithm np-complete

问题描述

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

529