- cc.complexity-theory np parameterized-complexity clique
- Updated Sat, 25 Jun 2022 19:40:55 GMT

Let $0\le p\le 1$ and consider the decision problem

CLIQUE$_p$

Input:integer $s$, graph $G$ with $t$ vertices and $\lceil p\binom{t}{2} \rceil$ edges

Question:does $G$ contain a clique on at least $s$ vertices?

An instance of CLIQUE$_p$ contains a proportion $p$ out of all possible edges. Clearly CLIQUE$_p$ is easy for some values of $p$. CLIQUE$_0$ contains only completely disconnected graphs, and CLIQUE$_1$ contains complete graphs. In either case, CLIQUE$_p$ can be decided in linear time. On the other hand, for values of $p$ close to $1/2$, CLIQUE$_p$ is NP-hard by a reduction from CLIQUE itself: essentially, it is enough to take the disjoint union with the Turn graph $T(t,s-1)$.

My question:

Is CLIQUE$_p$ either in PTIME or NP-complete for every value of $p$? Or are there values of $p$ for which CLIQUE$_p$ has intermediate complexity (if P NP)?

This question arose from a related question for hypergraphs, but it seems interesting in its own right.

I assume that the number $\left\lceil p \binom{t}{2} \right\rceil$ in the definition of the problem CLIQUE_{p} is exactly equal to the number of edges in the graph, unlike gphilips comment to the question.

The problem CLIQUE_{p} is NP-complete for any rational constant 0<*p*<1 by a reduction from the usual CLIQUE problem. (The assumption that *p* is rational is only required so that $\lceil pN \rceil$ can be computed from *N* in time polynomial in *N*.)

Let *k*3 be an integer satisfying both *k*^{2}1/*p* and (11/*k*)(12/*k*)>*p*. Given a graph *G* with *n* vertices and *m* edges along with a threshold value *s*, the reduction works as follows.

- If
*s*<*k*, we solve the CLIQUE problem in time O(*n*^{s}) time. If there is a clique of size at least*s*, we produce a fixed yes-instance. Otherwise, we produce a fixed no-instance. - If
*n*<*s*, we produce a fixed no-instance. - If
*n**s**k*, we add to*G*a (*k*1)-partite graph where each set consists of*n*vertices which has exactly $\left\lceil p \binom{nk}{2} \right\rceil - m$ edges, and produce this graph.

Note that the case 1 takes O(*n*^{k1}) time, which is polynomial in *n* for every *p*. The case 3 is possible because if *n**s**k*, then $\left\lceil p \binom{nk}{2} \right\rceil - m$ is nonnegative and at most the number of edges in the complete (*k*1)-partite graph K_{n,,n} as shown in the following two claims.

**Claim 1**. $\left\lceil p \binom{nk}{2} \right\rceil - m \ge 0$.

**Proof**. Since $m \le \binom{n}{2}$, it suffices if we prove $p \binom{nk}{2} \ge \binom{n}{2}$, or equivalently *pnk*(*nk*1) *n*(*n*1). Since *p* 1/*k*^{2}, we have *pnk*(*nk*1) *n*(*n*1/*k*) *n*(*n*1). **QED**.

**Claim 2**. $\left\lceil p \binom{nk}{2} \right\rceil - m \lt n^2 \binom{k-1}{2}$. (Note that the right-hand side is the number of edges in the complete (k1)-partite graph K_{n,,n}.)

**Proof**. Since $\lceil x \rceil \lt x+1$ and *m* 0, it suffices if we prove $p \binom{nk}{2} + 1 \le n^2 \binom{k-1}{2}$, or equivalently *n*^{2}(*k*1)(*k*2) *pnk*(*nk*1) 2 0. Since *p* < (11/*k*)(12/*k*), we have
$$n^2(k-1)(k-2) - pnk(nk-1) - 2$$
$$\ge n^2(k-1)(k-2) - n \left( n-\frac{1}{k} \right) (k-1)(k-2) - 2$$
$$= \frac{n}{k} (k-1)(k-2) - 2 \ge (k-1)(k-2) - 2 \ge 0.$$
**QED**.

*Edit*: The reduction in Revision 1 had an error; it sometimes required a graph with negative number of edges (when *p* was small). This error is fixed now.

External links referenced by this document: