Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR15-013 | 28th January 2015 16:51

On Hardness of Approximating the Parameterized Clique Problem


Authors: Subhash Khot, Igor Shinkar
Publication: 30th January 2015 10:35
Downloads: 1001


In the $Gap-clique(k, \frac{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 $\frac{k}{2}$. It is an open question in the study of fixed parameterized tractability whether the $Gap-clique(k, \frac{k}{2})$ problem is fixed parameter tractable, i.e., whether it has an algorithm that runs in time $f(k)\cdot n^\alpha$, where $f(k)$ is an arbitrary function of the parameter $k$ and the exponent $\alpha$ is a constant independent of $k$.

In this paper, we give some evidence that the $Gap-clique(k, \frac{k}{2})$ problem is not fixed parameter tractable. Specifically, we define a constraint satisfaction problem, which we call $Deg-2-sat$, where the input is a system of $k'$ quadratic equations in $k'$ variables over a finite field ${\mathbb F}$ of size $n'$, and the goal is to decide whether there is a solution in ${\mathbb F}$ that satisfies all the equations simultaneously. The main result in this paper is an ``FPT-reduction" from $Deg-2-sat$ to the $Gap-clique(k, \frac{k}{2})$ problem. If one were to hypothesize that the $Deg-2-sat$ problem is not fixed parameter tractable, then our reduction would imply that the $Gap-clique(k, \frac{k}{2})$ problem is not fixed parameter tractable either. The reduction relies on the algebraic techniques used in proof of the PCP theorem.

ISSN 1433-8092 | Imprint