ECCC-Report TR15-013https://eccc.weizmann.ac.il/report/2015/013Comments and Revisions published for TR15-013en-usFri, 30 Jan 2015 10:35:12 +0200
Paper TR15-013
| On Hardness of Approximating the Parameterized Clique Problem |
Subhash Khot,
Igor Shinkar
https://eccc.weizmann.ac.il/report/2015/013In 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.
Fri, 30 Jan 2015 10:35:12 +0200https://eccc.weizmann.ac.il/report/2015/013