# A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
## 3 FPT Hardness of Approximation
### Hardness from Gap Hypotheses
Later, the PCP Theorem confirms that these problems are NP-hard. In our case of FPT inapproximability, PIH seems to be a good analogy of MAX-SNP for problems in \(\textsc{W}[1]\) and, as mentioned before, PIH has been used as a starting point of many hardness of approximation results. However, there has not yet been many reverse reductions to PIH, and this is one of the motivation behind Question 7 above. Despite the aforementioned applications of PIH, there are still quite a few questions that seem out of reach of PIH, such as whether there is an \(o(k)\) factor FPT approximation for \(k\)-Clique or questions related to running time lower bounds of approximation algorithms. On this front, another stronger conjecture called the Gap Exponential Time Hypothesis (Gap-ETH) is often used instead:  
**Hypothesis 2** (Gap Exponential Time Hypothesis (Gap-ETH) [52; 53]). : _For some constants \(\varepsilon,\delta>0\), there is no \(O(2^{\delta n})\)-time algorithm that can, given a 3 CNF formula, distinguish between the following two cases:_  
* _(Completeness) the formula is satisfiable._
* _(Soundness) any assignment violates more than_ \(\varepsilon\) _fraction of the clauses._ _Here_ \(n\) _denotes the number of clauses_ _[_54_]__._  
Clearly, Gap-ETH is a strengthening of ETH, which can be thought of in the above form but with \(\varepsilon=1/n\). Another interesting fact is that Gap-ETH is stronger than PIH. This can be shown via the standard reduction from 3 SAT to \(k\)-Clique that establishes \(N^{\Omega(k)}\) lower bound for the latter. The reduction, due to Chen et al. [55; 56], proceed as follows. First, we partition the set of clauses \(C\) into \(C_{1},\ldots,C_{k}\) each of size \(n/k\). For each \(C_{i}\), we create a partition \(V_{i}\) in the new graph where each vertex corresponds to all partial assignments (to variables that appear in at least one clause of \(C_{k}\)) that satisfy all the clauses in \(C_{k}\). Two vertices are connected if the corresponding partial assignments are consistent, i.e., they do not assign a variable to different values. If there is an assignment that satisfies all the clauses, then clearly the restrictions of this assignment to each clause corresponds to \(k\) vertices from different partitions that form a clique. On the other hand, it is also not hard to argue that, in the soundness case, the number of edges induced by any \(k\) vertices from different partitions is at most \(1-\Theta(\varepsilon)\). Thus, Gap-ETH implies PIH as claimed. Now that we have demonstrated that Gap-ETH is at least as strong as PIH, we may go further and ask how much more can we achieve from Gap-ETH, compared to PIH. The obvious consequences of Gap-ETH is that it can give explicit running time lower bounds for FPT hardness of approximation results. Perhaps more surprising, however, is that it can be used to improve the inapproximability ratio as well. The rest of this subsection is devoted to present some of these examples, together with brief overviews of how the proofs of these results work.