2023/04/15 by Yijia Chen, Chen, Yijia, Yi Feng +5
Computer Science · #68Q17 #68Q27 #Algorithms and Data Compression #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #G.2.1 #G.2.2 #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.2304.07516
openalex publication_date 2023/04/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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. The recent breakthrough of Bingkai Lin [STOC'21] and subsequent works by Karthik C.S. and Khot [CCC'22], and by Lin, Ren, Sun Wang [ICALP'22] give a technique that bypasses Gap-ETH, thus leading to the inapproximability ratio of O(1) and ko(1) under W[1]-hardness (the first two) and ETH (for the latter one). All the work along this line follows the framework developed by Lin, which starts from the k-vector-sum problem and requires some involved algebraic techniques. This paper presents an alternative framework for proving the W[1]-hardness of the ko(1)-FPT-inapproximability of k-Clique. Using this framework, we obtain a gap-producing self-reduction of k-Clique without any intermediate algebraic problem. More precisely, we reduce from (k,k-1)-Gap Clique to (qk, qk-1)-Gap Clique, for any function q depending only on the parameter k, thus implying the ko(1)-inapproximability result when q is sufficiently large. Our proof is relatively simple and mostly combinatorial. At the core of our construction is a novel encoding of k-element subset stemming from the theory of "network coding" and a "Sidon set" representation of a graph.