# A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
## 3 FPT Hardness of Approximation
### W[1]-Hardness of Gap Problems
#### 3.1.3 Parameterized Inapproximability of Steiner Orientation by Gap Amplification  
Gap amplification is a widely used technique in the classic literatures on (NP-)hardness of approximation (e.g., [41; 42; 43]). In fact, the arguably simplest proof of the PCP theorem, due to Dinur [43], is indeed via repeated gap amplification. The overall idea here is simple: we start with a hardness of approximation for a problem with small factor (e.g., \(1+1/n\)). At each step, we perform an operation that transforms an instance of our problem to another instance, in such a way that the gap becomes bigger; usually this new instance will also be bigger than our instance. By repeatedly applying this operation, one can finally arrive at a constant, or even super constant, factor hardness of approximation. There are two main parameters that determine the success/failure of such an approach: how large the new instance is compared to the old instance (i.e., size blow-up) and how large the new gap is compared to the old gap, in each operation. To see how these two come into the picture, let us first consider a case study where a (straightforward) gap amplification procedure does not work: \(k\)-Clique. The standard way to amplify the gap for \(k\)-Clique is through graph product. Recall that the (tensor) graph product of a graph \(G=(V,E)\) with itself, denoted by \(G^{\otimes 2}\), is a graph whose vertex set is \(V^{2}\) and there is an edge between \((u_{1},u_{2})\) and \((v_{1},v_{2})\) if and only if \((u_{1},v_{1})\in E\) and \((u_{2},v_{2})\in E\). It is not hard to check that, if we can find a clique of size \(t\) in \(G^{\otimes 2}\), then we can find one of size \(\sqrt{t}\) in \(G\) (and vice versa). This implies that, if we have an instance of clique that is hard to approximate to within a factor of \((1+\varepsilon)\), then we may take the graph product with itself which yields an instance of Clique that is hard to approximate to within a factor of \((1+\varepsilon)^{2}\). Now, let us imagine that we start with the hard instance of an exact version of \(k\)-Clique. We may think of this as being hard to approximate to within a factor of \((1-1/k)\). Hence, we may apply the above gap amplification procedure \(\log k\) times, resulting in an instance of Clique that is hard to approximate to within a factor of \((1-1/k)^{2^{\log k}}\), which is a constant bounded away from one (i.e., \(\approx 1/e\)). The bad news here is that the number of the vertices of the final graph is \(n^{2^{\log k}}=n^{k}\), where \(n\) is the number of vertices of the initial graph. This does not give any lower bound, because we can solve \(k\)-Clique in the original graph in \(n^{O(k)}\) time trivially! In the next subsection, we will see a simple way to prove hardness of approximating \(k\)-Clique, assuming stronger assumptions. However, it remains an interesting and important open question how to prove such hardness from a non-gap assumption:  
**Open Question 6**. : _Is it W[1]-hard or ETH-hard to approximate \(k\)-Clique to within a constant factor in FPT time?_  
Having seen a failed attempt, we may now move on to a success story. Remarkably, Wlodarczyk [44] recently managed to use gap amplification to prove hardness of approximation for connectivity problems, including the \(k\)-Steiner Orientation problem. Here we are given a mixed graph \(G\), whose edges are either directed or undirected, and a set of \(k\) terminal pairs \(\{(s_{i},t_{i})\}_{i\in[k]}\). The goal is to orient all the undirected edges in such a way that maximizes the number of \(t_{i}\) that can be reached from \(s_{i}\). The problem is known to be in XP [45] but is W[1]-hard even when all terminal pairs can be connected [46]. Starting from this W[1]-hardness, Wlodarczyk [44] devises a gap amplification step that implies a hardness of approximation with factor \((\log k)^{o(1)}\) for the problem. Due to the technicality of the gap amplification step, we will not go into the specifics in this survey.