# A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
## 2 Preliminaries
### Parameterized approximation algorithms  
We briefly specify the different types of algorithms we will consider. As already defined in the introduction, an FPT algorithm computes the optimum solution in \(f(k)n^{O(1)}\) time for some parameter \(k\) and computable function \(f:\mathbb{N}\to\mathbb{N}\) on inputs of size \(n\). The common choices of parameters are the standard parameters based on solution size, structural parameters, guarantee parameters, and dual parameters. An algorithm that computes the optimum solution in \(f(k)n^{g(k)}\) time for some parameter \(k\) and computable functions \(f,g:\mathbb{N}\to\mathbb{N}\), is called a slice-wise polynomial (XP) algorithm. If the parameter is the approximation factor, i.e., the algorithm computes a \((1+\varepsilon)\)-approximation in \(f(\varepsilon)n^{g(\varepsilon)}\) time, then it is called a polynomial-time approximation scheme (PTAS). The latter type of algorithm has been studied avant la lettre for quite a while. This is also true for the corresponding FPT algorithm, which computes a \((1+\varepsilon)\)-approximation in \(f(\varepsilon)n^{O(1)}\) time, and is referred to as an efficient polynomial-time approximation scheme (EPTAS). Note that if the standard parameterization of an optimization problem is W[1]-hard, then the optimization problem does not have an EPTAS (unless FPT = W[1]) [11]. Some interesting links between these algorithms, traditionally studied from the perspective of polynomial-time approximation algorithms, and parameterized complexity have been uncovered more recently [8; 11; 12; 13; 14; 15; 16]. As also mentioned in the introduction, a parameterized \(\alpha\)-approximation algorithm computes an \(\alpha\)-approximation in \(f(k)n^{O(1)}\) time for some parameter \(k\) on inputs of size \(n\). If \(\alpha\) can be set to \(1+\varepsilon\) for any \(\varepsilon>0\) and the runtime is \(f(k,\varepsilon)n^{g(\varepsilon)}\), then we obtain a parameterized approximation scheme (PAS) for parameter \(k\). Note that this runtime is only truly FPT if we assume that \(\varepsilon\) is constant. If we forbid this and consider \(\varepsilon\) as a parameter as well, i.e., the runtime should be of the form \(f(k,\varepsilon)n^{O(1)}\), then we obtain EPAS. **Kernelization. ** A further topic closely related to the FPT algorithms is kernelization. Here, the idea is that an instance is efficiently pre-processed by removing the \"easy parts\" so that only the NP-hard core of the instance remains. More concretely, a kernelization algorithm takes an instance \(I\) and a parameter \(k\) of some problem and computes a new instance \(I^{\prime}\) with parameter \(k^{\prime}\) of the same problem. The runtime of this algorithm is polynomial in the size of the input instance \(I\) and \(k\), while the size of the output \(I^{\prime}\) and \(k^{\prime}\) is bounded as a function of the input parameter \(k\). For optimization problems, it should also be the case that any optimum solution to \(I^{\prime}\) can be converted to an optimum solution of \(I\) in polynomial time. The new instance \(I^{\prime}\) is called the kernel of \(I\) (for parameter \(k\)). A fundamental result in fixed-parameter tractability is that an (optimization) problem parameterized by \(k\) is FPT if and only if it admits a kernelization algorithm for the same parameter [17]. However the size of the guaranteed kernel will in general be exponential (or worse) in the input parameter. Therefore, an interesting question is whether an NP-hard problem admits small kernels of polynomial size. This can be interpreted as meaning that the problem has a very efficient pre-processing algorithm, which can be used prior to solving the kernel. It also gives an additional dimension to the parameterized complexity landscape. Kernelization has played a fundamental role in the development of FPT algorithms, where a pre-processing step is often used to simplify the structure of the input instance.