Improved Hardness of Approximating k-Clique under ETH
share
In this paper, we prove that assuming the exponential time hypothesis (ETH), there is no f(k)· n^k^o(1/loglog 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 [Lin21, LRSW22]. The crux of our proof is a framework to construct gap-producing reductions for the problem. More precisely, we show that given an error-correcting code C:Σ_1^k→Σ_2^k' 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' in (k')^O(1)· n^O(log|Σ_2|/log|Σ_1|) time such that: ∙ If G has a clique of size k, then G' has a clique of size K, where K = (k')^O(1). ∙ If G has no clique of size k, then G' has no clique of size (1-ε)· K for some constant ε∈(0,1). We then construct such a code with k'=k^Θ(loglog k) and |Σ_2|=|Σ_1|^k^0.54, establishing the hardness results above. Our code generalizes the derivative code [WY07] into the case with a super constant order of derivatives.
READ FULL TEXT