如您所知，寻找最大独立集是 NP。是否有一种算法可以找出给定的图是否具有至少 k 个顶点的独立集？请注意，我们不想找到它。我们只是想知道是否存在这样的东西。
最佳答案
引用 Wikipedia :
In the independent set decision problem, the input is an undirected graph and a number k, and the output is a Boolean value: true if the graph contains an independent set of size k, and false otherwise.
这个问题是 NP 完全的。您的问题问的是同一个问题，只是措辞不同，因为图具有至少 k 个顶点的独立集当且仅当它具有恰好 k 个顶点的独立集.
这意味着您的问题也是 NP 完全问题。
关于algorithm - 图中的独立集，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3540877/