# A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
## 4 Algorithms
### Network Design
At the same time, both the SLSN\({}_{\mathcal{C}^{\star}}\) and SLSN\({}_{\mathcal{C}_{\lambda}}\) problems parameterized by the number of terminals are paraNP-hard [204], since they are generalizations of the Restricted Shortest Path problem (where there is exactly one terminal pair). A PAS can however be obtained for both of these problems (whenever \(\lambda\) is a constant), but for no other class \(\mathcal{C}\) of demand patterns [203]. **Theorem 25** ([203]). : _For any constant \(\lambda>0\), there is an FPTAS for the SLSN\({}_{\mathcal{C}_{\lambda}}\) problem. For the SLSN\({}_{\mathcal{C}_{\lambda}}\)-problem a \((1+\varepsilon)\)-approximation can be computed in \(4^{k}(n/\varepsilon)^{O(1)}\) time for any \(\varepsilon>0\), where \(k\) is the number of terminal pairs. Moreover, under Gap-ETH no \((5/3-\varepsilon)\)-approximation for SLSN\({}_{\mathcal{C}}\) can be computed in\(f(k)n^{O(1)}\) time for any \(\varepsilon>0\) and computable function \(f\), whenever \(\mathcal{C}\) is a recursively enumerable class for which \(\mathcal{C}\
ot\subseteq\mathcal{C}^{\star}\cup\mathcal{C}_{\lambda}\) for every constant \(\lambda\)._  
A notable special case is when all edge lengths are 1 but edge costs are arbitrary. Then \(\operatorname{SLSN}_{\mathcal{C}_{\lambda}}\) is polynomial time solvable for any constant \(\lambda\), while \(\operatorname{SLSN}_{\mathcal{C}^{\star}}\) is FPT parameterized by the number of terminals [203]. At the same time the parameterized approximation lower-bound of Theorem 25 is still valid for this case. It is not known however, whether constant approximation factors can be obtained for \(\operatorname{SLSN}_{\mathcal{C}}\) when \(\mathcal{C}\) is a class different from \(\mathcal{C}_{\lambda}\) and \(\mathcal{C}^{\star}\). More generally we may ask the following question. **Open Question 11**. : _Given some class of graphs \(\mathcal{C}\
ot\subseteq\mathcal{C}^{\star}\cup\mathcal{C}_{\lambda}\), which approximation factor \(\alpha_{\mathcal{C}}\) can be obtained in FPT time for \(\operatorname{SLSN}_{\mathcal{C}}\) parameterized by the number of terminals?_  
Turning to the TSP problem, a generalization of TSP introduces deadlines until which vertices need to be visited by the computed tour. A natural parameterization in this setting is the number of vertices that have deadlines. It can be shown [205] that no approximation better than 2 can be computed when using this parameter. Nevertheless, a 2.5-approximation can be computed in FPT time [205]. The algorithm will guess the order in which the vertices with deadlines are visited by the optimum solution. It then computes a \(3/2\)-approximation for the remaining vertices using Christofides algorithm [3]. The approximation ratio follows, since the optimum tour can be thought of as two tours, of which one visits only the deadline vertices, while the other contains all remaining vertices. The approximation algorithm incurs a cost of \(\operatorname{\textsc{Opt}}\) for the former, and a cost of \(\frac{3}{2}\cdot\operatorname{\textsc{Opt}}\) for the latter part of the optimum tour. **Theorem 26** ([205]). : _For the \(\operatorname{\textsc{DLTSP}}\) problem a \(2.5\)-approximation can be computed in \(O(k!\cdot k)+n^{O(1)}\) time, if the number of vertices with deadlines is \(k\). Moreover, no \((2-\varepsilon)\)-approximation can be computed in \(f(k)n^{O(1)}\) time for any \(\varepsilon>0\) and computable function \(f\), unless \(P=NP\)._  
Low dimensional metrics.Just as for clustering problems, another well-studied parameter in network design is the dimension of the underlying geometric space. A typical setting is when the input is assumed to be a set of points in some \(k\)-dimensional \(\ell_{p}\)-metric, where distances between points \(x\) and \(y\) are given by a function \(\operatorname{dist}(x,y)=(\sum_{i=1}^{k}|x_{i}-y_{i}|^{p})^{1/p}\). Two prominent examples are Euclidean metrics (where \(p=2\)) and Manhattan metrics (where \(p=1\)).