graph-theory - 对于具有 n 个顶点的图，是否有任何多项式时间算法可以找到 k 顶点独立集？

Question

对于具有 n 个顶点的图，我怎样才能找到一个 k 顶点独立集？（实际上，它不一定是多项式时间算法，只要它在 n = 200，k = 10 的合理时间内运行即可。）

Answer 1

如果 k 不固定，这是一个 NP 难题。如果 k 是固定的，则它是平凡多项式。此外，您最好在其他溢出站点之一上询问纯算法问题。

至于实用算法，你已经尝试过什么？即使像贪婪搜索这样简单的事情也可能适用于小问题。