众所周知，最大独立集是NP。有没有一个算法来找出一个给定的图是否有一个至少k个顶点的独立集？注意我们不想找到它。我们只是想知道这种东西是否存在。
最佳答案
引用Wikipedia：
在独立集决策问题中，输入是一个无向图和一个数字k，输出是一个布尔值：如果图包含一个大小为k的独立集，则为true，否则为false。
这个问题是np完全问题。你的问题问同样的问题，只是措辞不同，因为一个图有一个至少k个顶点的独立集，如果并且只有当它有一个完全k个顶点的独立集。
这意味着你的问题也是np完全的。
众所周知，最大独立集是NP。有没有一个算法来找出一个给定的图是否有一个至少k个顶点的独立集？注意我们不想找到它。我们只是想知道这种东西是否存在。
最佳答案
引用Wikipedia：
在独立集决策问题中，输入是一个无向图和一个数字k，输出是一个布尔值：如果图包含一个大小为k的独立集，则为true，否则为false。
这个问题是np完全问题。你的问题问同样的问题，只是措辞不同，因为一个图有一个至少k个顶点的独立集，如果并且只有当它有一个完全k个顶点的独立集。
这意味着你的问题也是np完全的。