当顶点权重可能为负时，最大权重独立集的近似算法

Question

最大权重独立集有很多近似算法。但他们大多数都假设非负面权重。是否有任何算法可用于负面权重？

Answer 1

忽略负重顶点。考虑任意独立设置，包括一个负重顶点。如果删除该顶点，则生成的集合仍然是一个独立集合，但是您已增加其总重量。