Reduction for the proof that COMBI $:= \{\langle G,k \rangle | G$ has Clique $\geq k$ or Independent Set $\geq k\}$ is NP complete

Question

Given the Language $COMBI := \{\langle G,k \rangle | G$ has Clique $\geq k$ or Independent Set $\geq k\}$. Proof that Combi is NP-complete.

I tried to reduce Clique <=p Combi. I had two different ideas:

• Let $f(\langle G,k\rangle) = \langle G,k\rangle$ so $\langle G,k\rangle \in$ CLIQUE $\Rightarrow f(\langle G,k\rangle)$ is trivial. Though I am puzzled with the case $f(\langle G,k\rangle) \in$ COMBI $\Rightarrow \langle G,k\rangle $. What is when I have only an Independent set $\geq k$ within $\langle G,k\rangle$ and no Clique $\geq k$. Then it would be in COMBI but not within CLIQUE.

• Let $f(\langle G,k\rangle) = \langle G´,k\rangle$ where $G´= \overline{G} \cup G$ as disjunctive union (two different components) and $\overline{G}$ is the complement graph so $\langle G,k\rangle \in$ CLIQUE $\Rightarrow f(\langle G,k\rangle) \in$ COMBI is trivial again, but the other case seems to be flawed due to the same reason as in the first try.

Where am I going wrong or do I have to make a completely different reduction $f$?

Answer 1

Let $\langle G=(V,E), k \rangle$ be an instance of CLIQUE with $k \ge 1$, and let $n=|V|$.

Let $S$ be a new set of $n$ additional vertices. Construct a new graph $G'=(V', E')$ with $V' = V \cup S$ and $E=E' \cup (S \times (E \cup S))$. Now consider an instance $\langle G', n+k \rangle$ of your problem.

If $G$ has a clique of size $k$ containing the vertices in $C \subseteq V$ then $G'$ has at least one clique of size at least $n+k$. Pick, e.g., the clique induced by $C \cup S$.

If $G'$ has a clique or an independent set of size $n+k$ then let $C$ be the set of vertices that induce such a clique or independent set set. Since $C \cap S \neq \emptyset$ and $|C| \ge 2$, $C$ cannot be an independent set and therefore it is a clique. Then $C' = C \setminus S$ is a clique of size at least $n+k-n=k$ that is also a subgraph of $G$.