# A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
## 4 Algorithms
### Network Design
The dimension \(k\) of the metric space has been studied as a parameter from the parameterized approximation point-of-view avant la lettre for quite a while. It was shown [206; 207] that both Steiner Tree and TSP are paraNP-hard for this parameter (since they are NP-hard even if \(k=2\)), and that they are APX-hard in general metrics [201; 208]. However, a PAS for Euclidean metrics both for the Steiner Tree and the TSP problems were shown to exist in the seminal work of Arora [167; 209]. The techniques are similar to those used for clustering, and we refer to Section 4.3.2 for an overview. **Theorem 27** ([167]). : _For the Steiner Tree and TSP problems a \((1+\varepsilon)\)-approximation can be computed in \(k^{O(\sqrt{k}/\varepsilon)^{k-1}}n^{2}\) time for any \(\varepsilon>0\), if the input consists of \(n\) points in \(k\)-dimensional Euclidean space._  
This result also holds for the \(t\)-MST and \(t\)-TSP problems [167], where the cheapest tree or tour, respectively, on at least \(t\) nodes needs to be found. In this case the runtime has to be multiplied by \(t\) however. A related setting is the parameterization by the doubling dimension of the underlying metric. That is, when the parameter \(k\) is the smallest integer such that any ball in the metric can be covered by \(2^{k}\) balls of half the radius. Any point set in a \(k\) dimensional \(\ell_{p}\)-metric has doubling dimension \(O(k)\)and thus the latter parameter generalizes the former. For the TSP problem the above theorem can be generalized [210] to a PAS parameterized by the doubling dimension. Theorem 28 ([210]): _For the TSP problem a \((1+\varepsilon)\)-approximation can be computed in \(2^{(k/\varepsilon)^{O(k^{2})}}n\log^{2}n\) time for any \(\varepsilon>0\), if the input consists of \(n\) points with doubling dimension \(k\)._  
Given that a PAS exists for Steiner Tree in the Euclidean case, it is only natural to ask whether this is also possible for low doubling metrics. Only a QPTAS is known so far [211]. Moreover, a related parameter is the highway dimension, which is used to model transportation networks. As shown by Feldmann et al. [212] the techniques of Talwar [211] for low doubling metrics can be generalized to the highway dimension to obtain a QPTAS as well. Again, it is quite plausible to assume that a PAS exists. Open Question 12: _Is there a PAS for Steiner Tree parameterized by the doubling dimension? Is there a PAS for either Steiner Tree or TSP parameterized by the highway dimension?_  
Directed Graphs.When considering directed input graphs (asymmetric metrics), the Directed Steiner Tree problem takes as input a terminal set and a special terminal called the root. The task is to compute a directed tree of minimum weight that contains a path from each terminal to the root. In general no \(f(k)\)-approximation can be computed in FPT time for any computable function \(f\), when the parameter \(k\) is the number of Steiner vertices in the optimum solution [202]. A notable special case is the unweighted Directed Steiner Tree problem, which for this parameter admits a PAS. The techniques here are the same as those used to obtain Theorem 24 for the undirected case. However, in contrast to the undirected case which admits a PSAKS, no polynomial-sized \((2-\varepsilon)\)-approximate kernelization exists for Directed Steiner Tree [202], unless NP\(\subseteq\)coNP/poly. It is an intriguing question whether a 2-approximate kernel exists. Open Question 13: _Is there a polynomial-sized \(2\)-approximate kernel for the unweighted Directed Steiner Tree problem parameterized by the number of Steiner vertices in the optimum solution?_  
If the parameter is the number of terminals, the (weighted) Directed Steiner Tree problem is FPT, using the same algorithm as for the undirected version [196, 197]. A different variant of Steiner Tree in directed graphs is the Strongly Connected Steiner Subgraph problem, where a terminal set needs to be strongly connected in the cheapest possible way.