Improved Hardness of Approximating k-Clique under ETH
Bingkai Lin, Xuandi Ren, Yican Sun, Xiuhan Wang · 2023
In this paper, we prove that assuming the exponential time hypothesis (ETH), there is no $f(k) \cdot n^{k^{o(1 / \log \log k)}}$-time algorithm that can decide whether an n-vertex graph contains a clique of size k or contains no clique of size $k / 2$, and no FPT algorithm can decide whether an input graph has a clique of size k or no clique of size $k / f(k)$, where $f(k)$ is some function in $k^{1-o(1)}$. Our results significantly improve the previous works [1], [2]. The crux of our proof is a framework to construct gap-producing reductions for the k-CLIQUE problem. More precisely, we show that given an error-correcting code $C: \Sigma_{1}^{k} \rightarrow \Sigma_{2}^{k^{\prime}}$ that is locally testable and smooth locally decodable in the parallel setting, one can construct a reduction which on input a graph G outputs a graph $G^{\prime}$ in $\left(k^{\prime}\right)^{O(1)} \cdot n^{O\left(\log \left|\Sigma_{2}\right| / \log \left|\Sigma_{1}\right|\right)}$ time such•if G has a clique of size k, then $G^{\prime}$ has a clique of size K, where $K=\left(k^{\prime}\right)^{O(1)}$.•if G has no clique of size k, then $G^{\prime}$ has no clique of size $(1-\varepsilon) \cdot K$ for some constant $\varepsilon \in(0,1)$.We then construct such a code with $k^{\prime}=k^{\Theta(\log \log k)}$ and $\left|\Sigma_{2}\right|=\left|\Sigma_{1}\right|^{k^{0.54}}$, establishing the hardness result above. Our code generalizes the derivative code [3] into the case with a super constant order of derivatives.