Paper detail

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

For every graph $G$, let $ω(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 $ε>0$, outputs a graph $G&#39;$ and an integer $k&#39;$ in $2^{Θ(k^5)}\cdot |G|^{O(1)}$-time such that (1) $k&#39;\le 2^{Θ(k^5)}$, (2) if $ω(G)\ge k$, then $ω(G&#39;)\ge k&#39;$, (3) if $ω(G)<k$, then $ω(G&#39;)< (1-ε)k&#39;$. This implies that no $f(k)\cdot |G|^{O(1)}$-time algorithm can distinguish between the cases $ω(G)\ge k$ and $ω(G)<k/c$ for any constant $c\ge 1$ and computable function $f$, unless $FPT= W[1]$.