# A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
## 3 FPT Hardness of Approximation
### Hardness from Gap Hypotheses
#### 3.2.1 Strong Inapproximability of \(k\)-Clique  
Our first example is the \(k\)-Clique problem. Obviously, we can approximate \(k\)-Clique to within a factor of \(k\), by just outputting any single vertex. It had long been asked whether an \(o(k)\)-approximation is achievable in FPT time. As we saw above, PIH implies that a constant factor FPT approximation does not exist, but does not yet resolve this question. Nonetheless, assuming Gap-ETH, this question can be resolved in the negative:  
**Theorem 5** ([39]).: _Assuming Gap-ETH, there is no \(o(k)\)-FPT-approximation for \(k\)-Clique._  
The reduction used in [39] to prove the above inapproximability is just a simple modification of the above reduction [55; 56] that we saw for \(k\)-Clique. Suppose that we would like to rule out a \(\frac{k}{\delta}\)-approximation, where \(g=g(k)\) is a function such that \(\lim_{k\to\infty}g(k)=\infty\). The only change in the reduction is that, instead of letting \(C_{1},\ldots,C_{k}\) be the partition of the set of clauses \(C\), we let each \(C_{i}\) be a set of \(\frac{Dn}{g}\) clauses for some sufficiently large constant \(D>0\). The rest of the reduction works similar to before: for each \(C_{i}\), we create a vertex corresponding to each partial assignment that satisfies all the clauses in \(C_{i}\). Two vertices are joined by an edge if and only if they are consistent. This completes the description of the reduction.  
To see that the reduction yields Theorem 5, first note that, if there is an assignment that satisfies the CNF formula, then we can again pick the restrictions on this formula onto \(C_{1},\ldots,C_{k}\); these gives \(k\) vertices that induces a clique in the graph.  
On the other hand, suppose that every assignment violates more than an \(\varepsilon\) fraction of clauses. We will argue that there is no clique of size \(g\) in the constructed graph. The only property we need from the subsets \(C_{1},\ldots,C_{k}\) is that the union of any \(g\) such subsets contain at least \((1-\varepsilon)\) fraction of the clauses. It is not hard to show that this is true with high probability, when we choose \(D\) to besufficiently large. Now, suppose for the sake of contradiction that there exists a clique of size \(g\) in the graph. Since the vertices corresponding to the same subset \(C_{i}\) form an independent set, it must be that these \(g\) vertices are from different subsets. Let us call these subsets \(C_{i_{1}},\cdots,C_{i_{g}}\). Because these vertices induce a clique, we can find a global assignment that is consistent with each vertex. This global assignment satisfies all the clauses in \(C_{i_{1}}\cup\cdots\cup C_{i_{g}}\). However, \(C_{i_{1}}\cup\cdots\cup C_{i_{g}}\) contains at least \(1-\varepsilon\) fraction of all clauses, which contradicts to our assumption that every assignment violates more than \(\varepsilon\) fraction of the clauses.  
Now, if we can \(o(k)\)-approximate \(k\)-Clique in \(T(k)\cdot N^{O(1)}\) time. Then, we may run this algorithm to distinguish the two cases in Gap-ETH in \(f(k)\cdot(2^{Dn/g})^{O(1)}=2^{o(n)}\) time, which violates Gap-ETH. This concludes our proof sketch. We end by remarking that the reduction may also be viewed as an instantiation of the randomized graph product [57; 41; 58], and it can also be derandomized. We omit the details of the latter here. Interested readers may refer to [39] for more detail.