启发式查找任意图中的最大权重独立集
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) \in E（不带邻居）
和
x(v) \in {0, 1}（只能选择取或不取一个顶点）
这是一个组合问题（最后一个约束是顶点数量的指数）。有两种方法可以从这里继续：
将最后一个约束切换为
x(v) \in [0, 1]（您选择顶点的范围）
用 LP 求解器求解，然后继续this paper, 4.3。
在下面的评论中，David Eisenstat 声称对于图形的大小，整数求解器会很好（并产生更好的结果）
这是为 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 是最小加权独立集。
要求解 MWIS，您可以在补图上使用最大权重团求解器。 TSM-MWC is a fast algorithm implemented in C. If you graphs aren't too large, you may be able to solve the problem using Networkx in Python: here are reference pages for the complement and max_weight_clique 个函数。
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) \in E（不带邻居）
和
x(v) \in {0, 1}（只能选择取或不取一个顶点）
这是一个组合问题（最后一个约束是顶点数量的指数）。有两种方法可以从这里继续：
将最后一个约束切换为
x(v) \in [0, 1]（您选择顶点的范围）
用 LP 求解器求解，然后继续this paper, 4.3。
在下面的评论中，David Eisenstat 声称对于图形的大小，整数求解器会很好（并产生更好的结果）
这是为 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 是最小加权独立集。
要求解 MWIS，您可以在补图上使用最大权重团求解器。 TSM-MWC is a fast algorithm implemented in C. If you graphs aren't too large, you may be able to solve the problem using Networkx in Python: here are reference pages for the complement and max_weight_clique 个函数。