Abstract
The kClique problem is a canonical hard problem in parameterized complexity. In this paper, we study the parameterized complexity of approximating the kClique problem where an integer k and a graph G on n vertices are given as input, and the goal is to find a clique of size at least k/F(k) whenever the graph G has a clique of size k. When such an algorithm runs in time T(k) ⋅ poly(n) (i.e., FPTtime) for some computable function T, it is said to be an F(k)FPTapproximation algorithm for the kClique problem.
Although, the nonexistence of an F(k)FPTapproximation algorithm for any computable sublinear function F is known under gapETH [Chalermsook et al., FOCS 2017], it has remained a long standing open problem to prove the same inapproximability result under the more standard and weaker assumption, W[1]≠FPT.
In a recent breakthrough, Lin [STOC 2021] ruled out constant factor (i.e., F(k) = O(1)) FPTapproximation algorithms under W[1]≠FPT. In this paper, we improve this inapproximability result (under the same assumption) to rule out every F(k) = k^{1/H(k)} factor FPTapproximation algorithm for any increasing computable function H (for example H(k) = log^∗ k).
Our main technical contribution is introducing list decoding of Hadamard codes over large prime fields into the proof framework of Lin.
BibTeX  Entry
@InProceedings{karthikc.s._et_al:LIPIcs.CCC.2022.6,
author = {Karthik C. S. and Khot, Subhash},
title = {{Almost Polynomial Factor Inapproximability for Parameterized kClique}},
booktitle = {37th Computational Complexity Conference (CCC 2022)},
pages = {6:16:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772419},
ISSN = {18688969},
year = {2022},
volume = {234},
editor = {Lovett, Shachar},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16568},
URN = {urn:nbn:de:0030drops165680},
doi = {10.4230/LIPIcs.CCC.2022.6},
annote = {Keywords: Parameterized Complexity, kclique, Hardness of Approximation}
}
Keywords: 

Parameterized Complexity, kclique, Hardness of Approximation 
Collection: 

37th Computational Complexity Conference (CCC 2022) 
Issue Date: 

2022 
Date of publication: 

11.07.2022 