algorithm - 图中的独立集

Question

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

Answer 1

引用维基百科：

在独立集决策问题中，输入是无向图和数字k，输出是布尔值：如果图包含大小为k的独立集，则为 true ，否则为 false。

这个问题是NP完全的。您的问题提出了相同的问题，只是措辞不同，因为当且仅当图具有恰好由k个顶点组成的独立集合时，它才具有至少由k个顶点组成的独立集合。

这意味着您的问题也是 NP 完全的。

Answer 2

最大独立集的大小有一个很好的下界（“图独立数”由 alpha 表示），

其中 d(v) 是顶点 v 的度数，总和是简单图 G 的所有顶点。它是由 Wei 和 Caro 独立发现的（我在“根据度”，JR Griggs），并且对于不同类型的图还有其他下限。

这意味着一个最大独立集将至少有 k 个顶点，其中 k 由这个下限给出。