启发式在任意图中找到最大权重独立集

Question

MWIS（最大权重无关集）是NP完全问题，因此如果P！= NP，我们无法在足够好的时间复杂度中找到解。

我正在寻找一种算法，可以在良好的时间复杂度内找到任意图形中MWIS的近似值。我目前正在研究一个包含128个节点和3051个边缘的连通图。

我找到了this paper，但它似乎只适用于具有独特MWIS的二分图。

如果有人可以帮我提供一些参考资料，或者甚至更好地使用工作算法的伪代码，我将很高兴。

Answer 1

可以将此表述为以下问题。假设图中的每个顶点v具有权重w（v）。您定义变量x（v），并使用一些开箱即用的线性编程求解器来解决

max \ sum_v w（v）x（v）（最大化所选顶点的权重）

受制于

E中的x（u）+ x（v）<= 1，（u，v）\（不要占邻居）

和

x（v）\ in {0,1}（只能选择取或不取顶点）

---

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

• 将最后一个约束切换为 x（v）\ in [0,1]（选择顶点的程度） 用LP解算器解决它，并继续沿着this paper, 4.3。
• 在下面的评论中，David Eisenstat声称，对于图表的大小，整数求解器会很好（并产生更好的结果）

Answer 2

这是用于找到MWIS的最小加权度顶点的代码，如@Ami引用的文章中所建议的。

import networkx as nx
import numpy as np
graph = nx.generators.random_graphs.barabasi_albert_graph(50,10)
for u in graph:
    graph.nodes[u]['weight'] = np.random.uniform(0,1)

adj_0 = nx.adj_matrix(graph).todense()
a = -np.array([graph.nodes[u]['weight'] for u in graph.nodes])
IS = -np.ones(adj_0.shape[0])
while np.any(IS==-1):
    rem_vector = IS == -1
    adj = adj_0.copy()
    adj = adj[rem_vector, :]
    adj = adj[:, rem_vector]

    u = np.argmin(a[rem_vector].dot(adj!=0)/a[rem_vector])
    n_IS = -np.ones(adj.shape[0])
    n_IS[u] = 1
    neighbors = np.argwhere(adj[u,:]!=0)
    if neighbors.shape[0]:
        n_IS[neighbors] = 0
    IS[rem_vector] = n_IS
print IS

IS是最小加权独立集。