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


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.