Constant Approximating k-Clique is W[1]-hard

Abstract

For every graph $G$, let $\omega (G)$ be the largest size of complete subgraph in $G$. This paper presents a simple algorithm which, on input a graph $G$, a positive integer $k$ and a small constant $\epsilon >0$, outputs a graph $G^{\prime }$ and an integer $k^{\prime }$ in $2^{\Theta (k^5)}\cdot |G{|}^{O(1)}$-time such that (1) $k^{\prime }\le 2^{\Theta (k^5)}$, (2) if $\omega (G)\ge k$, then $\omega (G^{\prime })\ge k^{\prime }$, (3) if $\omega (G)<k$, then $\omega (G^{\prime })<(1-\epsilon )k^{\prime }$. This implies that no $f(k)\cdot |G{|}^{O(1)}$-time algorithm can distinguish between the cases $\omega (G)\ge k$ and $\omega (G)<k/c$ for any constant $c\ge 1$ and computable function $f$, unless $FPT=W[1]$.