# A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
## 5 Future Directions
### Parameterized Running Times  
The quality of FPT algorithms is mainly measured in the obtainable runtime. Given a parameter \(k\), for some problems the optimum solution can be computed in \(f(k)n^{\delta(k)}\) time, for some functions \(f\) and \(g\) independent of the input size \(n\) (i.e., the degree of the polynomial also depends on the parameter). If such an algorithm exists the problem is slice-wise polynomial (XP), and the algorithm is called an XP algorithm. A typical example is if a solution of size \(k\) is to be found within a data set of size \(n\), in which case often an \(n^{O(k)}\) time exhaustive search algorithm exists. However, an FPT algorithm with runtime, say, \(O(2^{k}n)\) is a lot more efficient than an XP algorithm with runtime \(n^{O(k)}\), and therefore the aim is usually to find FPT algorithms, while XP algorithms are counted as prohibitively slow. The discovery of the W-hierarchy in complexity theory has paved the way to providing evidence when an FPT algorithm is unlikely to exist. Assuming ETH, it is even possible to provide lower bounds on the runtimes obtainable by any FPT or XP algorithm. Similar to approximation algorithms, this has lead to the discovery of a spectrum of tractability (cf. [6]): starting from slightly sub-exponential \(2^{O(\sqrt{k})}n^{O(1)}\) time, through single exponential \(2^{O(k)}n^{O(1)}\) time, to double exponential \(2^{2^{O(k)}}n^{O(1)}\) time for FPT algorithms with matching asymptotic lower bounds under ETH (e.g., for the Planar Vertex Cover, Vertex Cover, and Edge Clique Cover problems, respectively, each parameterized by the solution size). For XP algorithms, asymptotically tight runtime bounds of the form \(n^{O(\sqrt{k})}\) and \(n^{O(k)}\) can be obtained under ETH (e.g., for the Clique problem parameterized by the solution size, and the Planar Bidirected Steiner Network problem parameterized by the number of terminals [50], respectively). Finally, problems that are NP-hard when the given parameter is constant do not even allow XP algorithms unless P = NP (e.g., the Graph Colouring problem where the parameter is the number of colours). In terms of tight runtime bounds, existing results on parameterized approximation algorithms are few and far between. In particular, most of them show that for a given parameter \(k\) one of the following cases applies. * An approximation is possible in \(f(k)n^{O(1)}\) time for some function \(f\). Most current results are only concerned with the existence of an algorithm with this type of runtime, i.e., they do not provide any evidence that the obtained runtime is best possible, or try to optimize it. The only lower bounds known exclude certain types of approximation schemes when a hardness result for the parameterization by the solution size exists. For instance, it is known that if some problem does not admit a \(2^{o(k)}n^{O(1)}\) time algorithm for this parameter \(k\) then it also does not admit an EPTAS with runtime \(2^{o(1/\varepsilon)}n^{O(1)}\) (cf. [5; 8]). * A certain approximation ratio cannot be obtained in \(f(k)n^{O(1)}\) time for any function \(f\). For example, it is known that while a 2-approximation for the Strongly Connected Steiner Subgraph problem can be computed in \(2^{O(k)}n^{O(1)}\) time [215], where \(k\) is the number of terminals, no \((2-\varepsilon)\)-approximation can be computed in \(f(k)n^{O(1)}\) time [50] for any function \(f\), under Gap-ETH (cf. Section 4.4). Hence, matching lower bounds on the time needed to compute an approximation are missing. For example, is the runtime of \(2^{O(k)}n^{O(1)}\) best possible to compute a 2-approximation for the Strongly Connected Steiner Subgraph problem? Could there be a \(2^{O(\sqrt{k})}n^{O(1)}\) time algorithm to compute a 2-approximation as well? For PASs the exact obtainable runtime is often elusive, even if certain types of approximation schemes can be excluded.