证明 CLIQUE-OR-INDEPENDENT-SET 的 NP-completeness
Prove NP-completeness of CLIQUE-OR-INDEPENDENT-SET
首先，我想提一下，这是我的作业。但是，为了解决我的问题，我可以使用任何我想要的文献。
虽然我觉得这个问题从它的名字就很清楚了，我还是给它描述一下："For given undirected graph G and given integer k, does G contain totally connected (clique) subgraph of size k or totally disconnected subgraph (independent set) of size k."
我知道从 3-SAT 到 CLIQUE 以及从 3-SAT 到 INDEPENDENT-SET 的多项式约简。 (http://mlnotes.com/2013/04/29/npc.html) 但是，我对此有疑问，因为我无法将这两种减少结合起来。我也试过从 CLIQUE 减少到 CLIQUE-OR-INDEPENDENT-SET 但没有成功。
所以，如果有任何提示，我将不胜感激！
提前致谢。
我发现问题从 INDEPENDENT-SET 减少到 CLIQUE-OR-INDEPENDENT-SET。您需要做的就是将 n 个孤立的顶点添加到图 G 中（它是 INDEPENDENT-SET 的一个实例并且有 n 个顶点）。我们将这个新创建的图称为 G'（CLIQUE-OR-INDEPENDENT-SET 的实例）。那么不难证明 G 有 k 个独立集当且仅当 G' 有 n+k 个独立的团集（因为根据构造，它不能有 n+k派系).
首先，我想提一下，这是我的作业。但是，为了解决我的问题，我可以使用任何我想要的文献。
虽然我觉得这个问题从它的名字就很清楚了，我还是给它描述一下："For given undirected graph G and given integer k, does G contain totally connected (clique) subgraph of size k or totally disconnected subgraph (independent set) of size k."
我知道从 3-SAT 到 CLIQUE 以及从 3-SAT 到 INDEPENDENT-SET 的多项式约简。 (http://mlnotes.com/2013/04/29/npc.html) 但是，我对此有疑问，因为我无法将这两种减少结合起来。我也试过从 CLIQUE 减少到 CLIQUE-OR-INDEPENDENT-SET 但没有成功。
所以，如果有任何提示，我将不胜感激！
提前致谢。
我发现问题从 INDEPENDENT-SET 减少到 CLIQUE-OR-INDEPENDENT-SET。您需要做的就是将 n 个孤立的顶点添加到图 G 中（它是 INDEPENDENT-SET 的一个实例并且有 n 个顶点）。我们将这个新创建的图称为 G'（CLIQUE-OR-INDEPENDENT-SET 的实例）。那么不难证明 G 有 k 个独立集当且仅当 G' 有 n+k 个独立的团集（因为根据构造，它不能有 n+k派系).