algorithm - 简单图 |V|= 10^6，度数 4 : Maximum Independent Subset?

Question

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

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

一般情况下是NP难的。

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

Answer 1

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

For instance, for sparse graphs (graphs in which the number of edges is at most a constant times the number of vertices in any subgraph), the maximum clique has bounded size and may be found exactly in linear time;^[6] however, for the same classes of graphs, or even for the more restricted class of bounded degree graphs, finding the maximum independent set is MAXSNP-complete, implying that, for some constant c (depending on the degree) it is NP-hard to find an approximate solution that comes within a factor of c of the optimum.^[7]

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