4
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.