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.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
answered Oct 5, 2015 at 20:52