# A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
## 3 FPT Hardness of Approximation
### Hardness from Gap Hypotheses  
In the previous subsection, we have seen that several hardness of approximation results can be proved based on standard assumptions. However, as alluded to briefly, some basic problems, including \(k\)-Clique, still evades attempts at proving such results. This motivates several researchers in the community to come up with new assumptions that allow more power and flexibility in proving inapproximability results. We will take a look at two of these hypotheses in this subsection; we note that there have also been other assumptions formulated, but we only focus on these two since they arguably have been used most often. The first assumption, called the Parameterized Inapproximability Hypothesis (PIH) for short, can be viewed as a gap analogue of the \(\textsc{W}[1]\
eq\textsc{FPT}\) assumption. There are many (equivalent) ways to state PIH. We choose to state it in terms of an inapproximability of the colored version of Densest \(k\)-Subgraph. In Multicolored Densest \(k\)-Subgraph, we are given a graph \(G=(V,E)\) where the vertex set \(V\) is partition in to \(k\) parts \(V_{1},\ldots,V_{k}\). The goal is to select \(k\) vertices \(v_{1}\in V_{1},v_{2}\in V_{2},\ldots,v_{k}\in V_{k}\) such that \(\{v_{1},\ldots,v_{k}\}\) induces as many edges as possible. It is easy to see that the exact version of this problem is \(\textsc{W}[1]\)-hard, via a straightforward reduction from \(k\)-Clique. PIH postulates that even the approximate version of this problem is hard:  
**Hypothesis 1** (Parameterized Inapproximability Hypothesis (PIH) [47, 48]). : _For some constant \(\varepsilon>0\), there is no \((1+\varepsilon)\) factor FPT approximation algorithm for Multicolored Densest \(k\)-Subgraph._  
There are two important remarks about PIH. First, the factor \((1+\varepsilon)\) is not important, and the conjecture remains equivalent even if we state it for a factor \(C\) for any arbitrarily large constant \(C\); this is due to gap amplification via parallel repetition [42]. Second, PIH implies that \(k\)-Clique is hard to approximate to within any constant factor:  
**Lemma 1**. : _Assuming PIH, there is no constant factor FPT approximation algorithm for \(k\)-Clique._  
The above result can be shown via a classic reduction of Feige, Goldwasser, Lovasz, Safra and Szegedy (henceforth FGLSS) [49], which was one of the first works connecting proof systems and hardness of approximation. Specifically, the FGLSS reduction transforms \(G\) to another graph \(G^{\prime}\) by viewing the edges of \(G\) as vertices of \(G^{\prime}\). Then, we connect \(\{u_{1},v_{1}\}\) and \(\{u_{2},v_{2}\}\) except when the union \(\{u_{1},v_{1}\}\cup\{u_{2},v_{2}\}\) contains two distinct vertices from the same partition. One can argue that the size of the largest clique in \(G^{\prime}\) is exactly equal to the number of edges in the optimal solution of Multicolored Densest \(k\)-Subgraph on \(G\). As a result, PIH implies hardness of approximation of the former. Interestingly, however, it is not known if the inverse is true and this remains an interesting open question:  
**Open Question 7**. : _Does PIH hold if we assume that \(k\)-Clique is FPT inapproximable to within any constant factor?_  
As demonstrated by the FGLSS reduction, once we have a gap, it is much easier to give a reduction to another hardness of approximation result, because we do not have to create the initial gap ourselves (as in the previous subsection) but only need to preserve or amplify the gap. Indeed, PIH turns out to be a pretty robust hypothesis that gives FPT inapproximability for many problems, including \(k\)-Clique, Directed Odd Cycle Traversal[48] and Strongly Connected Steiner Subgraph[50]. We remark that the current situation here is quite similar to that of the landscape of the classic theory of hardness of approximation before the PCP Theorem [21, 22] was proved. There, Papadimitriou and Yannakakis introduced a complexity class MAX-SNP and show that many optimization problems are hard (or complete) for this class [51].