Hardness of a special GAP-CLIQUE problem

In the GAP-CLIQUE$(k,\ell)$ problem, we are given a graph $G$ over $n$ vertices and have to decide whether $G$ contains a clique of size $k$ or no clique of size $\ell$. Using a PCP system, it can be shown that GAP-CLIQUE$(k,\varepsilon k)$ is NP-hard for any positive constant $\varepsilon$ less or equal to $1$. In fact, even GAP-CLIQUE$(k,n^{\varepsilon - 1}k)$ is NP-hard. However, I am interested in GAP-CLIQUE instances, where $k$ and $\ell$ depend on the size of $G$. In particular, I am wondering if GAP-CLIQUE$(3/4n,1/4n)$ is NP-hard.

The problem is solvable in polynomial time, using the following algorithm:


Keep removing pairs of unconnected vertices, until a clique remains.

If the graph has a clique of size $(3/4)n$, then the clique you end up with contains at least $n/4$ vertices (exercise).

Source: Boppana and Halldórsson, Alon and Kahale.

StackExchange Computer Science Q#47890, answer score: 4