群-或无关集的NP-完备性证明

Question

首先，我想提一下，这是我的作业。然而，为了解决我的问题，我可以使用任何我想要的文献。

尽管我认为这个问题从名称上是明确的，但我将给出它的描述：“对于给定的无向图G和给定的整数k，G包含大小为k的全连通(团)子图还是完全不连通的子图(独立集)。”

我知道多项式约简从3-SAT到CLIQUE，从3-SAT到INDEPENDENT-SET。(http://mlnotes.com/2013/04/29/npc.html)然而，我对这一项有问题，因为我不能将这两项削减合并起来。我也尝试过从CLIQUE减少到CLIQUE-OR-INDEPENDENT-SET，但没有成功。

所以我真的很感激任何提示！

提前谢谢。

Answer 1

我发现了从problem INDEPENDENT-SET到CLIQUE-OR-INDEPENDENT-SET的简化。您所需要做的就是将n孤立的顶点添加到图G (这是INDEPENDENT-SET的一个实例，并具有n顶点)。让我们调用这个新创建的图G' (CLIQUE-OR-INDEPENDENT-SET实例)。然后，不难证明G有k独立集当且仅当G'有n+k独立集团集(因为，通过构造，它不能有n+k团)。