# A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
## 4 Algorithms
### Network Design
: _For the Steiner Tree problem a \((1+\varepsilon)\)-approximation can be computed in \((2+\delta)^{(1-\varepsilon/2)}n^{O(1)}\) time for any constant \(\delta>0\) (and in \(2^{(1-\varepsilon/2)}n^{O(1)}\) time in the unweighted case) for any \(\varepsilon>0\), where \(k\) is the number of terminals. Moreover, a \((1+\varepsilon)\)-approximate kernel of size \((k/\varepsilon)^{O(2^{1/\varepsilon})}\) can be computed in polynomial time._  
A natural alternative to the number of terminals is to consider the vertices remaining in the optimum tree after removing the terminals: a folklore result states that Steiner Tree is W[2]-hard parameterized by the number of non-terminals (called Steiner vertices) in the optimum solution. At the same time, unless P = NP there is no PTAS for the problem, as it is APX-hard [201]. However an approximation scheme is obtainable when parametrizing by the number of Steiner vertices \(k\) in the optimum, and also a PSAKS is obtainable under this parameterization. To obtain both of these results, Dvorak et al. [202] devise a reduction rule that is based on the following observation: if the optimum tree contains few Steiner vertices but many terminals, then the tree must contain (1) a large component containing only terminals, or (2) a Steiner vertex that has many terminal neighbours. Intuitively, in case (2) we would like to identify a large star with terminal leaves and small cost in the current graph, while in case (1) we would like to find a cheap edge between two terminals. Note that such a single edge also is a star with terminal leaves. The reduction rule will therefore find the star with minimum weight per contained terminal, which can be done in polynomial time. This rule is applied until the number of terminals, which decreases after each use, falls below a threshold depending on the input parameter \(k\) and the desired approximation ratio \(1+\varepsilon\). Once the number of terminals is bounded by a function of \(k\) and \(\varepsilon\), the Dreyfus and Wagner [196] algorithm can be applied on the remaining instance, or a kernel can be computed using the PSAKS of Theorem 23. It can be shown that the reduction rule does not distort the optimum solution by much as long as the threshold is large enough, which implies the following theorem. **Theorem 24** ([202]). : _For the Steiner Tree problem a \((1+\varepsilon)\)-approximation can be computed in \(2^{O(k^{2}/\varepsilon^{4})}n^{O(1)}\) time for any \(\varepsilon>0\), where \(k\) is the number of non-terminals in the optimum solution. Moreover, a \((1+\varepsilon)\)-approximate kernel of size \((k/\varepsilon)^{2^{O(1/\varepsilon)}}\) can be computed in polynomial time._  
This theorem is also generalizable to the Steiner Forest problem, where a list of terminal pairs is given and the task is to find a minimum weight forest in the input graph connecting each pair. In this case though, the parameter has to be combined with the number of connected components of the optimum forest [202]. A variation of the Steiner Forest problem is the Shallow-Light Steiner Network (SLSN) problem. Here a graph with both edge costs and edge lengths is given, together with a set of terminal pairs and a length threshold \(L\). The task is to compute a minimum cost subgraph, which connects each terminal pair with a path of length at most \(L\). For this problem a dichotomy result was shown [203] in terms of the pattern given by the terminal pairs. More precisely, the terminal pairs are interpreted as edges in a graph for which the vertices are the terminals: if \(\mathcal{C}\) is some class of graphs, then SLSN\({}_{\mathcal{C}}\) is the Shallow-Light Steiner Network problem restricted to sets of terminal pairs that span some graph in \(\mathcal{C}\). Let \(\mathcal{C}^{\star}\) denote the class of all stars, and \(\mathcal{C}_{\lambda}\) the class of graphs with at most \(\lambda\) edges. The SLSN\({}_{\mathcal{C}^{\star}}\) problem is APX-hard [201], as it is a generalization of Steiner Tree (where \(L=\infty\)).