5
$\begingroup$

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?

$\endgroup$
0

2 Answers 2

6
$\begingroup$

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

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

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

$\endgroup$

Your Answer

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

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