# A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
## 2 Preliminaries
### Parameterized approximation algorithms
It is therefore only natural to consider such pre-processing algorithms for parameterized approximation algorithms as well. Lokshtanov et al. [18] define an \(\alpha\)-approximate kernelization algorithm, which computes a kernel \(I^{\prime}\) such that any \(\beta\)-approximation in \(I^{\prime}\) can be converted into an \(\alpha\beta\)-approximation to the input instance \(I\) in polynomial time. Again, the size of \(I^{\prime}\) and \(k^{\prime}\) need to be bounded as a function of the input parameter \(k\), and the algorithm needs to run in polynomial time. The instance \(I^{\prime}\) is now called an \(\alpha\)-approximate kernel. Analogous to exact kernels, any problem has a parameterized \(\alpha\)-approximation algorithm if and only if it admits an \(\alpha\)-approximate kernel for the same parameter [18], which however might be of exponential size in the parameter. An \(\alpha\)-approximate kernelization algorithm that computes a polynomial-sized kernel, and for which we may set \(\alpha\) to \(1+\varepsilon\) for any \(\varepsilon>0\), is called a polynomial-sized approximate kernelization scheme (PSAKS). In this case \(\varepsilon\) is necessarily considered to be a constant, since any kernelization algorithms needs to run in polynomial time. We remark here that apart from \(\alpha\)-approximate kernels, there is another common workaround for problems with no polynomial kernels, captured using the notion of Turing kernels. There is also a lower bound framework for Turing kernels [19], and the question of approximate kernels for problems that do not even admit Turing kernels is fairly natural to ask. However we skip this discussion for the sake of brevity. Finally, note that in literature, there is another notion of approximate kernels called \(\alpha\)-fidelity kernelization [20] which is different from the one mentioned above. Essentially, an \(\alpha\)-fidelity kernel is a polynomial time preprocessing procedure such that an optimal solution to the reduced instance translates to an \(\alpha\)-approximate solution to the original. This definition allows a loss of precision in the preprocessing step, but demands that the reduced instance has to be solved to optimality. See [18] for a detailed discussion on the differences between the two approximate kernel notions. **Complexity-Theoretic Hypotheses. ** We assume that the readers have basic knowledge of (classic) parameterized complexity theory, including the W-hierarchy, the exponential time hypothesis (ETH), and the strong exponential time hypothesis (SETH). The reader may choose to recapitulate these definitions by referring to [6] (Sections 13 and 14). We will additionally discuss two hypotheses that may not be standard to the community. The first is the Gap Exponential Time Hypothesis (Gap-ETH), which is a strengthening of ETH. Roughly speaking, it states that even the approximate version of 3 SAT cannot be solved in subexponential time; a more formal statement of Gap-ETH can be found in Hypothesis 2. Another hypothesis we will discuss is the Parameterized Inapproximability Hypothesis (PIH), which states that the multicolored version of the Densest \(k\)-Subgraph is hard to approximate in FPT time. Once again, we do not define PIH formally here; please refer to Hypothesis 1 for a formal statement.