TR15-013 Authors: Subhash Khot, Igor Shinkar

Publication: 30th January 2015 10:35

Downloads: 1388

Keywords:

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.