Prove NP-completeness of CLIQUE-OR-INDEPENDENT-SET

Question

First of all, I want to mention that this is my homework. However, to solve my problem I can use any literature I want.

Even though I think that problem is clear from its name, I will give it description: "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."

I know about polynomial reductions from 3-SAT to CLIQUE and from 3-SAT to INDEPENDENT-SET. (http://mlnotes.com/2013/04/29/npc.html) However, I have problem with this one because I cannot combine those two reductions. I also tried reduction from CLIQUE to CLIQUE-OR-INDEPENDENT-SET but without much success.

So I would really appreciate any hints!

Thanks in advance.

Answer 1

I found out reduction from problem INDEPENDENT-SET to CLIQUE-OR-INDEPENDENT-SET. All you need to do is to add n isolated vertices to graph G (which is an instance of INDEPENDENT-SET and has n vertices). Let call this newly created graph G' (instance of CLIQUE-OR-INDEPENDENT-SET). Then it is not hard to prove that G has k independent-set iff G' has n+k independent-set of clique (since, by construction, it cannot have n+kclique).