On Hardness of Approximating the Parameterized Clique Problem
Subhash Khot, Igor Shinkar · 2016
In the Gap-clique (k, k/2) problem, the input is an n-vertex graph G, and the goal is to decide whether G contains a clique of size k or contains no clique of size k/2. It is an open question in the study of fixed parameterized tractability whether the Gap-clique (k, k/2) problem is fixed parameter tractable, i.e., whether it has an algorithm that runs in time f(k) ⋅ nα, where f(k) is an arbitrary function of the parameter k and the exponent α is a constant independent of k.