# A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
## 5 Future Directions
### Approximation Factors  
The quality of a polynomial-time approximation algorithm is mainly measured by the obtainable approximation factor \(\alpha\): the smaller it is the more feasibly solvable the problem is. Therefore, a lot of work has been invested into determining the smallest obtainable approximation factor \(\alpha\) for all kinds of computationally hard problems. In the non-parameterized (i.e., NP-hardness) world, a whole spectrum of approximability has been discovered (cf. [3,4]): the most feasibly solvable NP-hard problems (e.g., the Knapsack problem) admit a so-called polynomial-time approximation scheme (PTAS), which is an algorithm computing a \((1+\varepsilon)\)-approximation for any given constant \(\varepsilon>0\). Some problems can be shown not to admit a PTAS (under reasonable complexity assumptions), but still allow constant approximation factors (e.g., the Steiner Tree problem). Yet others can only be approximated within a polylogarithmic factor (e.g., the Set Cover problem), while some are even harder than this, as the best approximation factor obtainable is polynomial in the input size (e.g., the Clique problem). In contrast to polynomial-time approximation algorithms, a full spectrum of obtainable approximation ratios is still missing when allowing parameterized runtimes. Instead, only some scattered basic results are known. In particular, most of parameterized approximation problems belongs to one of the following categories:  
* A parameterized approximation scheme (PAS) exists, i.e., for any constant \(\varepsilon>0\) a \((1+\varepsilon)\)-approximation can be computed in \(f(k)n^{O(1)}\) time for some parameter \(k\). These are currently the most prevalent types of results in the literature. To just mention one example, the Steiner Tree problem is APX-hard, but admits a PAS [202] when parameterized by the number of non-terminals (so-called Steiner vertices) in the optimum solution (cf. Section 4.4). * A lower bound excluding any non-trivial approximation factor exists. For example, under ETH the Dominating Set problem has no \(g(k)\)-approximation in \(f(k)n^{o(k)}\) time [35] for any functions \(g\) and \(f\), where \(k\) is the size of the largest dominating set. * A polynomial-time approximation algorithm can achieve a similar approximation ratio, i.e., the parameterization is not very helpful. For instance, for the \(k\)-Center problem [286] a 2-approximation can be computed in polynomial time [287], but even when parameterizing by \(k\) no \((2-\varepsilon)\)-approximation is possible [187] for any \(\varepsilon>0\), under standard complexity assumptions. A similar situation holds for Max \(k\)-Coverage, which we discussed in Section 4.2.2. * Constant or logarithmic approximation ratios can be shown, and which beat any approximation ratio obtainable in polynomial time. For instance, Strongly Connected Steiner Subgraph problem : under standard complexity assumptions, for this problem no polynomial-time \(O(\log^{2-\varepsilon}n)\)-approximation algorithm exists [214], and there is no FPT algorithm parameterized by the number \(k\) of terminals [213]. However it is not hard to compute a 2-approximation in \(2^{O(k)}n^{O(1)}\) time [215], and no \((2-\varepsilon)\)-approximation algorithm with runtime \(f(k)n^{O(1)}\) exists [50] under Gap-ETH, for any function \(f\) and any \(\varepsilon>0\) (cf. Section 4.4). For many problems discussed in this survey, including Densest \(k\)-Subgraph, Steiner Tree with bounded doubling/highway dimension, it has not been determined which category they belong. There are also a lot of problems in the final category for which asymptotically tight approximation ratios have not been found, including Directed Multicut, Treewidth \(k\)-Deletion (both weighted and unweighted). The parameterized approximability of \(\mathcal{H}\)-Minor Deletion for non-planar \(\mathcal{H}\) is also widen open except Minimum Planarization (\(\mathcal{H}=\{K_{5},K_{3,3}\}\)) [259].