algorithm - 图中的独立集

Question

如您所知，寻找最大独立集是 NP。是否有一种算法可以找出给定的图是否具有至少 k 个顶点的独立集？请注意，我们不想找到它。我们只是想知道是否存在这样的东西。

Answer 1

引用 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 完全问题。