Hardness of parameterized CLIQUE?

Question

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 Turán 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.

Answer 1

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 gphilip’s 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²≥1/p and (1−1/k)(1−2/k)>p. Given a graph G with n vertices and m edges along with a threshold value s, the reduction works as follows.

1. 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.
2. If n<s, we produce a fixed no-instance.
3. 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^k−1) 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², 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 (k−1)-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²(k−1)(k−2) − pnk(nk−1) − 2 ≥ 0. Since p < (1−1/k)(1−2/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.

Answer 2

If $p$ can be a function of $t$, then the problem can be intermediate. Set up $p$ so that the number of edges will be say $\log^4 t$. Then obviously $s$ can be at most $\log^2 t$ and hence there is a $t^{\log^2 t}$ algorithm for this problem, meaning that the problem (under standard assumptions, say SAT doesn't have subexponential algorithms) cannot be NP hard.

On the other hand, this problem is harder than the standard clique problem on $\log^2 t$ vertices (you can always place all the edges on those vertices and ignore the rest). And so again, under the same assumption the problem doesn't have a polynomial time algorithm.

If $p$ is a constant then it's always NP hard as gphilip said.