简单图| V | = 10^6，度4：最大独立子集？

给出一个含有100万个顶点的最大度数为4的简单图。简单图| V | = 10^6，度4：最大独立子集？

我们想要查找最大独立子集。

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

度数是4的事实提供了一个有效的解决方案来计算它吗？

来源

2012-08-02 Andrew Tomazos

您的意思是？ http://en.wikipedia.org/wiki/Independent_set_%28graph_theory%29 – 2012-08-02 16:57:09

@ DennisMeng：是的，谢谢，我已经更新了这个问题以使用正确的术语。 – 2012-08-02 17:02:25

进一步读入，维基百科页面，我发现这个关于这个问题：

例如，对于稀疏图（图中的边缘的数量是最多的恒定倍数的顶点数量任何子图），最大集团有界限大小，并可能发现完全线性时间;然而，对于相同类别的图表，或者甚至对于更受限类别的有界度图，寻找最大独立集合是MAXSNP完全的，这意味着，对于某些常数c（取决于度），难以找到一个近似解决方案，它的最优解是c的一个因子。 ^[7]

你的情况是有限度的情况下，所以从这个片段来看，你更严格的版本仍然是NP难。

来源

2012-08-02 17:09:19

这是因为图中的最大独立集相当于图的补充中的最大集团（图中具有刚好从第一图中缺失的边的集合）。如果一个是有界的，另一个不是。 – chepner 2012-08-02 20:21:57

参考文献[5]可以通过谷歌搜索找到，它显示独立集已经是3次图的完整的MAXSNP。 – sdcvvc 2012-08-06 17:17:49

有一个非常简单的贪婪1/5逼近。取任何顶点，将其添加到独立集，并从图中移除邻居。继续，直到没有顶点。这个技巧更通用的版本是Turan's theorem。

来源

2012-08-06 17:16:15 sdcvvc

如果您在维基百科页上阅读，它引用了一个参考文献，说如果您选择最低-degree顶点而不是只是一个任意的顶点，你会得到2的因子。 – 2012-08-06 21:34:00

简单图| V | = 10^6，度4：最大独立子集？

回答

相关问题