On Hardness of Approximating the Parameterized Clique Problem

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.

In this paper, we give some evidence that the Gap-clique(k, 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 F of size n', and the goal is to decide whether there is a solution in 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, 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, k/2) problem is not fixed parameter tractable either. The reduction relies on the algebraic techniques used in proof of the PCP theorem.