Almost Polynomial Factor Inapproximability for Parameterized k-Clique

C. S. Karthik, Subhash Khot

Research output: Chapter in Book/Report/Conference proceedingConference contribution


The k-Clique problem is a canonical hard problem in parameterized complexity. In this paper, we study the parameterized complexity of approximating the k-Clique 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., FPT-time) for some computable function T, it is said to be an F(k)-FPT-approximation algorithm for the k-Clique problem. Although, the non-existence of an F(k)-FPT-approximation algorithm for any computable sublinear function F is known under gap-ETH [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)) FPT-approximation algorithms under W[1]≠FPT. In this paper, we improve this inapproximability result (under the same assumption) to rule out every F(k) = k1/H(k) factor FPT-approximation 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.

Original languageEnglish (US)
Title of host publication37th Computational Complexity Conference, CCC 2022
EditorsShachar Lovett
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772419
StatePublished - Jul 1 2022
Event37th Computational Complexity Conference, CCC 2022 - Philadelphia, United States
Duration: Jul 20 2022Jul 23 2022

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Conference37th Computational Complexity Conference, CCC 2022
Country/TerritoryUnited States


  • Hardness of Approximation
  • Parameterized Complexity
  • k-clique

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Almost Polynomial Factor Inapproximability for Parameterized k-Clique'. Together they form a unique fingerprint.

Cite this