reduction - 证明 CLIQUE-OR-INDEPENDENT-SET 的 NP 完备性

Question

首先，我想提一下，这是我的功课。但是，为了解决我的问题，我可以使用任何我想要的文献。

尽管我认为这个问题从它的名字就很清楚了，但我还是会给出描述：“对于给定的无向图 G 和给定的整数 k，G 是否包含大小为 k 的完全连通（团）子图或完全不连通子图（独立集）尺寸 k。”

我知道从3-SATtoCLIQUE和 from 3-SATto 的多项式归约INDEPENDENT-SET。（http://mlnotes.com/2013/04/29/npc.html）但是，我对此有疑问，因为我无法将这两种减少结合起来。我也尝试从CLIQUEto减少，CLIQUE-OR-INDEPENDENT-SET但没有多大成功。

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

提前致谢。

Answer 1

我发现从问题减少INDEPENDENT-SET到CLIQUE-OR-INDEPENDENT-SET. 您需要做的就是将n孤立的顶点添加到图形G（这是一个实例INDEPENDENT-SET并具有n顶点）。让我们称这个新创建的图G'（的实例CLIQUE-OR-INDEPENDENT-SET）。那么不难证明G有k独立集当且仅当G'具有n+k派的独立集（因为，通过构造，它不能有n+k派）。