Simple Combinatorial Construction of the k o (1) -Lower Bound for Approximating the Parameterized k -Clique
Yijia Chen, Yi Feng, Bundit Laekhanukit, Yanlin Liu · Society for Industrial and Applied Mathematics eBooks · 2025
In the parameterized k-clique problem, or k-Clique for short, we are given a graph G and a parameter k ≥ 1. The goal is to decide whether there exist k vertices in G that induce a complete subgraph (i.e., a k-clique). This problem plays a central role in the theory of parameterized intractability as one of the first W[1]-complete problems. Existing research has shown that even an FPT-approximation algorithm for k-Clique with arbitrary ratio does not exist, assuming the Gap-Exponential-Time Hypothesis (Gap- ETH) [Chalermsook et al., FOCS’17 and SICOMP]. However, whether this inapproximability result can be based on the standard assumption of W[1] ≠ FPT remains unclear.