On Lower Bounds of Approximating Parameterized k-Clique
share
Given a simple graph G and an integer k, the goal of 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 [Lin21]. We study the approximation of k-Clique under the Exponential Time Hypothesis (ETH). The reduction of [Lin21] already implies an n^Ω(√(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) algorithm to approximate k-Clique within a constant factor, then PIH is true.
READ FULL TEXT