# A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
## 1 Introduction  
In their seminal papers of the mid 1960s, Cobham [1] and Edmonds [2] independently phrased what is now known as the Cobham-Edmonds thesis. It states that an optimization problem is feasibly solvable if it admits an algorithm with the following two properties:  
1. Accuracy: the algorithm should always compute the best possible (optimum) solution. 2. Efficiency: the runtime of the algorithm should be polynomial in the input size \(n\). Shortly after the Cobham-Edmonds thesis was formulated, the development of the theory of NP-hardness and reducibility identified a whole plethora of problems that are seemingly intractable, i.e., for which algorithms with the above two properties do not seem to exist. Even though the reasons for this phenomenon remain elusive up to this day, this has not hindered the development of algorithms for such problems. To obtain an algorithm for an NP-hard problem, at least one of the two properties demanded by the Cobham-Edmonds thesis needs to be relaxed. Ideally, the properties are relaxed as little as possible, in order to stay close to the notion of feasible solvability suggested by the thesis. A very common approach is to relax the accuracy condition, which means aiming for approximation algorithms [3, 4]. The idea here is to use only polynomial time to compute an \(\alpha\)-approximation, i.e., a solution that is at most a factor \(\alpha\) times worse than the optimum solution obtainable for the given input instance. Such an algorithm may also be randomized, i.e., there is either a high probability that the output is an \(\alpha\)-approximation, or the runtime is polynomial in expectation. In a different direction, several relaxations of the efficiency condition have also been proposed. Popular among these is the notion of parameterized algorithms [5, 6]. Here the input comes together with some parameter \(k\in\mathbb{N}\), which describes some property of the input and can be expected to be small in typical applications. The idea is to isolate the seemingly necessary exponential runtime of NP-hard problems to the parameter, while the runtime dependence on the input size \(n\) remains polynomial. In particular, the algorithm should compute the optimum solution in \(f(k)n^{O(1)}\) time,for some computable function \(f:\mathbb{N}\to\mathbb{N}\) independent of the input size \(n\). If such an algorithm exists for a problem it is fixed-parameter tractable (FPT), and the algorithm is correspondingly referred to as an FPT algorithm. Approximation and FPT algorithms have been studied extensively for the past few decades, and this has lead to a rich literature on algorithmic techniques and deep links to other research fields within mathematics. However, in this process the limitations of these approaches have also become apparent. Some NP-hard problems can fairly be considered to be feasibly solvable in the respective regimes, as they admit polynomial-time algorithms with rather small approximation factors, or can be shown to be solvable optimally with only a fairly small exponential runtime overhead due to the parameter. However, many problems can also be shown not to admit any reasonable algorithms in either of these regimes, assuming some standard complexity assumptions. Thus considering only approximation and FPT algorithms, as has been mostly done in the past, we are seemingly stuck in a swamp of problems for which we have substantial evidence that they cannot be feasibly solved. To find a way out of this dilemma, an obvious possibility is to lift both the accuracy and the efficiency requirements of the Cobham-Edmonds thesis. In this way, we obtain a parameterized \(\alpha\)-approximation algorithm, which computes an \(\alpha\)-approximation in \(f(k)n^{O(1)}\) time for some computable function \(f\), given an input of size \(n\) with parameter \(k\). The study of such algorithms had been suggested dating back to the early days of parameterized complexity (cf.