# Reduce $\sqrt{n}$-CLIQUE to CLIQUE

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 < \sqrt{n}$? It seems we need to be able to remove vertices without disturbing the size of the largest clique. My idea in this case to remove a vertex if it has less than $c-1$ edges. Obviously the new graph has a clique of size $c$ if and only if the original graph does. But what happens if we can't remove enough vertices? Can we conclude that if a graph has $n > c^2$ vertices each with degree $\geq c$ then a clique exists?

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

• Ah, thanks! That's very clever -- didn't think to increase $c$.
– MCT
Oct 23, 2016 at 22:14

Below is a different reduction from CLIQUE to $$\sqrt{n}$$-CLIQUE which is essentially an extension of the reduction from CLIQUE to $$\frac{n}{2}$$-CLIQUE.

Given an instance $$(G=(V,E),k)$$ of CLIQUE, we construct an instance $$G'=(V',E')$$ of $$\sqrt{n}$$-CLIQUE as follows. Suppose $$V=\{v_1,...,v_n\}$$, then $$G'$$ is defined as follows $$V'=V\cup\{u_1,...,u_{n-k}\}\cup\{w_1,...,w_{n^2-2n+k}\}$$ $$E'=E\cup\{\{u_i,u_j\}\mid \forall i,j\in[n-k]\}\cup\{\{v_{i},u_j\}\mid \forall i\in[n],\forall j\in[n-k]\}$$ Intuitively, we are constructing $$G'$$ to have one copy of $$G$$ which is fully connected to a $$K_{n-k}$$ clique, and we pad the number of vertices to $$n^2$$ using isolated vertices.

Claim: $$(G=(V,E),k)\in$$ CLIQUE if and only if $$G'\in\sqrt{n}$$-CLIQUE.

proof. $$\Longrightarrow$$ If $$(G=(V,E),k)\in$$ CLIQUE, then the copy of $$G$$ in $$G'$$ has a clique of size $$\geq k$$. Since $$G$$ in $$G'$$ is fully connected to $$K_{n-k}$$, $$G'$$ will have a clique of size $$\geq (n-k)+k=n$$.

$$\Longleftarrow$$ If $$G'\in\sqrt{n}$$-CLIQUE, then suppose for contradiction that $$G$$ has all cliques of size $$. This implies that $$G'$$ has all cliques of size $$<(n-k)+k=n$$. A contradiction. Thus $$G$$ has a clique of size $$\geq k$$.

Finally, it is easy to construct $$G'$$ in poly$$(n)$$-time. So we are done.