patternMinor
Reduce $\sqrt{n}$-CLIQUE to CLIQUE
Viewed 0 times
sqrtreduceclique
Problem
Recall that $G$ has a clique of size $k$ if it has a complete sub graph consisting of $k$ vertices. Define CLIQUE as the decision problem
$$\{ \langle G, c \rangle \mid G \text{ has a clique of size } c\}$$
Define the problem $\sqrt{n}$-CLIQUE as follows:
$$\{\langle G \rangle \mid G \text{ has a clique of at least size } \sqrt{n}\}$$
where $n$ is the number of vertices of $G$. It is easy to reduce $\sqrt{n}$-CLIQUE to CLIQUE. How can we go the other way and thereby show that $\sqrt{n}$-CLIQUE is NP-complete?
Idea: If $c \geq \sqrt{n}$, we can add dummy vertices to $G$ until $c = \sqrt{n}$. What do we do if $c c^2$ vertices each with degree $\geq c$ then a clique exists?
$$\{ \langle G, c \rangle \mid G \text{ has a clique of size } c\}$$
Define the problem $\sqrt{n}$-CLIQUE as follows:
$$\{\langle G \rangle \mid G \text{ has a clique of at least size } \sqrt{n}\}$$
where $n$ is the number of vertices of $G$. It is easy to reduce $\sqrt{n}$-CLIQUE to CLIQUE. How can we go the other way and thereby show that $\sqrt{n}$-CLIQUE is NP-complete?
Idea: If $c \geq \sqrt{n}$, we can add dummy vertices to $G$ until $c = \sqrt{n}$. What do we do if $c c^2$ vertices each with degree $\geq c$ then a clique exists?
Solution
When $c > \sqrt{n}$, you add an independent set of size $m$ so that $c = \sqrt{n+m}$ (i.e., you need $m = c^2-n$).
When $c < \sqrt{n}$, try doing the same, increasing both $n$ and $c$ at the same time, by adding a complement of an independent set. (You might need to add a few isolated vertices as well.)
When $c < \sqrt{n}$, try doing the same, increasing both $n$ and $c$ at the same time, by adding a complement of an independent set. (You might need to add a few isolated vertices as well.)
Context
StackExchange Computer Science Q#65014, answer score: 6
Revisions (0)
No revisions yet.