简单图|V|= 10^6，度4:最大无关子集？

Question

您将看到一个最大度为4的简单图，其中有100万个顶点。

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

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

次数是最大值4这一事实是否提供了计算它的有效解决方案？

Answer 1

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