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'$ and an integer $k'$ in $2^{Θ(k^5)}\cdot |G|^{O(1)}$-time such that (1) $k'\le 2^{Θ(k^5)}$, (2) if $ω(G)\ge k$, then $ω(G')\ge k'$, (3) if $ω(G)<k$, then $ω(G')< (1-ε)k'$. 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]$.

No reviews yet.

No comments yet.