Hardness of parameterized CLIQUE? 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.
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.