2026-08-17T03:36:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16431 2024-03-06T10:57:28Z ddc:004 open_access

On Lower Bounds of Approximating Parameterized k-Clique Lin, Bingkai Ren, Xuandi Sun, Yican Wang, Xiuhan parameterized complexity k-clique hardness of approximation Given a simple graph G and an integer k, the goal of the k-Clique problem is to decide if G contains a complete subgraph of size k. We say an algorithm approximates k-Clique within a factor g(k) if it can find a clique of size at least k/g(k) when G is guaranteed to have a k-clique. Recently, it was shown that approximating k-Clique within a constant factor is W[1]-hard [Bingkai Lin, 2021]. We study the approximation of k-Clique under the Exponential Time Hypothesis (ETH). The reduction of [Bingkai Lin, 2021] already implies an n^Ω(√[6]{log k})-time lower bound under ETH. We improve this lower bound to n^Ω(log k). Using the gap-amplification technique by expander graphs, we also prove that there is no k^o(1) factor FPT-approximation algorithm for k-Clique under ETH. We also suggest a new way to prove the Parameterized Inapproximability Hypothesis (PIH) under ETH. We show that if there is no n^O(k/(log k))-time algorithm to approximate k-Clique within a constant factor, then PIH is true. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Bingkai Lin and Xuandi Ren and Yican Sun and Xiuhan Wang 2022 Is Part Of LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2022.90 urn:nbn:de:0030-drops-164317 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.90 eng https://creativecommons.org/licenses/by/4.0/legalcode