2

给你一个简单的最大度数为 4 的图，有 100 万个顶点。

我们想找到一个最大独立子集。

在一般情况下，它是 NP 难的。

度数最大为 4 的事实是否提供了计算它的有效解决方案？

4

2 回答 2

3

进一步阅读该维基百科页面，我发现了这个主题：

例如，对于稀疏图（边数最多是任何子图中顶点数的常数倍的图），最大团具有有界大小，并且可以精确地在线性时间内找到；[6]然而，对于相同类别的图，甚至对于更受限制的有界度图类别，找到最大独立集是 MAXSNP 完全的，这意味着对于某些常数 c（取决于度）它是 NP - 很难找到一个近似解，它在最优值的 c 倍范围内。[7]

你的案例是有界度案例，所以从这个片段来看，你的限制性更强的版本仍然是 NP-hard。

于 2012-08-02T17:09:19.633 回答
1

有一个非常简单的贪心 1/5 近似值。取任何顶点，将其添加到独立集，并从图中删除邻居。继续直到没有顶点。这个技巧的一个更一般的版本是图兰定理。

于 2012-08-06T17:16:15.557 回答