# A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
## 4 Algorithms
### Network Design  
In network design, the task is to connect some set of vertices in a metric, which is often given by the shortest-path metric of an edge-weighted graph. Two very prominent problems of this type are the Travelling Salesperson (TSP) and Steiner Tree problems. For TSP all vertices need to be connected in a closed walk (called a route), and the length of the route needs to be minimized [195]. For Steiner Tree a subset of the vertices (called terminals) is given as part of the input, and the objective is to connect all terminals by a tree of minimum weight in the metric (or graph). Both of these are fundamental problems that have been widely studied in the past, both on undirected and directed input graphs. **Undirected graphs. ** A well-studied parameter for Steiner Tree is the number of terminals, for which the problem has been known to be FPT since the early 1970s due to the work of Dreyfus and Wagner [196]. Their algorithm is based on dynamic programming and runs in \(3^{k}n^{O(1)}\) time if \(k\) is the number of terminals. Faster algorithms based on the same ideas with runtime \((2+\delta)^{k}n^{O(1)}\) for any constant \(\delta>0\) exist [197] (here the degree of the polynomial depends on \(\delta\)). The unweighted Steiner Tree problem also admits a \(2^{k}n^{O(1)}\) time algorithm [198] using a different technique based on subset convolution. Given any of these exact algorithms as a subroutine, a faster PAS can also be found [20] (cf. Section 4.7). On the other hand, no exact polynomial-sized kernel exists [130] for the Steiner Tree problem, unless NP\(\subseteq\)coNP/poly. Interestingly though, a PSAKS can be obtained [18]. This kernel is based on a well-known fact proved by Borchers and Du [199], which is very useful to obtain approximation algorithms for the Steiner Tree problem. It states that any Steiner tree can be covered by smaller trees containing few terminals, such that these trees do not overlap much. More formally, a full-component is a subtree of a Steiner tree, for which the leaves coincide with its terminals. For the optimum Steiner tree \(T\) and any \(\varepsilon>0\), there exist full-components \(C_{1},\ldots,C_{\ell}\) of \(T\) such that  
1. each full-component \(C_{i}\) contains at most \(2^{\lceil 1/\varepsilon\rceil}\) terminals (leaves),
2. the sum of the weights of the full-components is at most \(1+\varepsilon\) times the cost of \(T\), and
3. taking any collection of Steiner trees \(T_{1},\ldots,T_{\ell}\), such that each tree \(T_{i}\) connects the subset of terminals that forms the leaves of full-component \(C_{i}\), the union \(\bigcup_{i=1}^{\ell}T_{i}\) is a feasible solution to the input instance. Not knowing the optimum Steiner tree, it is not possible to know the subsets of terminals of the full-components corresponding to the optimum. However, it is possible to compute the optimum Steiner tree for every subset of terminals of size at most \(2^{\lceil 1/\varepsilon\rceil}\) using an FPT algorithm for Steiner Tree. The time to compute all these solutions is \(k^{O(2^{\lceil 1/\varepsilon})}n^{O(1)}\), using for instance the Dreyfus and Wagner [196] algorithm. Now the above three properties guarantee that the graph given by the union of all the computed Steiner trees, contains a \((1+\varepsilon)\)-approximation for the input instance. In fact, the best polynomial time approximation algorithm known to date [200] uses an iterative rounding procedure to find a \(\ln(4)\)-approximation of the optimum solution in the union of these Steiner trees. To obtain a kernel, the union needs to be sparsified, since it may contain many Steiner vertices and also the edge weights might be very large. However, Lokshtanov et al. [18] show that the number of Steiner vertices can be reduced using standard techniques, while the edge weights can be encoded so that their space requirement is bounded in the parameter and the cost of any solution is distorted by at most a \(1+\varepsilon\) factor. **Theorem 23** ([18; 20]).