On Lower Bounds of Approximating Parameterized k-Clique

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 W1-hard Lin21. We study the approximation of k-Clique under the Exponential Time Hypothesis (ETH). The reduction of Lin21 already implies an n^Ω (6{ k) }-time lower bound under ETH. We improve this lower bound to n^Ω (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{ k) } algorithm to approximate k-Clique within a constant factor, then PIH is true.