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

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$$?

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$$.