I assume that the number $\left\lceil p \binom{t}{2} \right\rceil$ in the definition of the problem CLIQUEp is exactly equal to the number of edges in the graph, unlike gphilip’s comment to the question.
The problem CLIQUEp 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 k2≥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.
- If s<k, we solve the CLIQUE problem in time O(ns) 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(nk−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 Kn,…,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/k2, 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 Kn,…,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 n2(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.