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

Question

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

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

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

如果有人能帮我提供一些参考资料，甚至是一个可行算法的伪代码，我将不胜感激。

- Laurent XU

Answer 1

可以将其表述为以下问题。假设图中每个顶点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求解器解决，并继续沿着本文4.3。

• 在下面的评论中，David Eisenstat声称对于您的图形大小，整数求解器效果很好（并且产生更好的结果）

- Ami Tavory

---

从经验来看，对于问题所提到的规模的图形，仅通过将约束条件x(v)在[0,1]中转换为x(v)在{0,1}中（使其成为整数程序），求解器本身就会返回最优解。否则，求解器对于整数程序的启发式方法在实践中可能比链接论文中描述的舍入方法更好。 - David Eisenstat

@DavidEisenstat 好的，谢谢。我已经将您的评论合并进去了。 - Ami Tavory

谢谢，我会尝试两种方法。我想确保我需要解决的LP松弛是max(w(v) x(v))，受限于(x(v1) + x(v2) <= 1)，如果v1和v2是相邻的。 你有没有用C++编写的LP Solver和IP Solver可以方便地使用？ - Laurent XU

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是最小加权独立集。

- pg2455

---

嗨@pg2455，这个算法能找到精确的最大权独立集吗？ - jolene

我无法编辑我的上面的评论，但刚刚重新仔细阅读了它：这个算法能用来找到最大加权独立集吗？ - jolene

这是一种启发式方法来寻找最小（而非最小值）的 WIS。您可以取反权重并使用此启发式方法来查找最大（而非最大值）的 WIS。该启发式方法可以找到满足一个标准（独立集属性）的解决方案，但无法证明它是确切最优的。因为 WIS 是 NP-Hard 问题，所以不可能在没有证明解决方案的最优性的情况下找到最大 WIS。您可能需要使用精确求解器来实现这一点。希望这能有所帮助！ - pg2455

啊，我明白了 - 谢谢！使用负权重的想法没有出现在我的脑海中。你知道有哪些精确求解器可以直接暴力解决问题吗？我正在尝试找到一些小图的最大独立集！ - jolene

我认为你可以很好地使用MIS的整数线性规划公式，并使用任何像SCIP这样的现成求解器，它将给出所有可能的MIS。 - pg2455

Answer 3

为了解决MWIS问题，您可以在补图上使用最大权重团算法。TSM-MWC是一种快速的C语言实现算法。如果您的图不太大，您也可以使用Python中的Networkx来解决这个问题：这里是complement和max_weight_clique函数的参考页面。

- James Trimble