# A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
## 4 Algorithms
### Network Design
This problem is W[1]-hard parameterized by the number of terminals [213], and no \(O(\log^{2-\varepsilon}n)\)-approximation can be computed in polynomial time [214], unless \(\mathrm{NP}\subseteq\mathrm{ZTIME}(n^{\mathrm{polylog}(n)})\). However, a 2-approximation can be computed in FPT time [215]. The crucial observation for this algorithm is that in any strongly connected solution, fixing some terminal as the root, every terminal can be reached from the root, while at the same time the root can be reached from each terminal. Thus the optimum solution is the union of two directed trees, of which one is directed towards the root and the other is directed away from the root, and the leaves of both trees are terminals. Hence it suffices to compute two solutions to the Directed Steiner Tree problem, which can be done in FPT time, to obtain a 2-approximation for Strongly Connected Steiner Subgraph. Interestingly, no better approximation is possible with this runtime [50]. Theorem 29 ([50, 215]): _For the Strongly Connected Steiner Subgraph problem a \(2\)-approximation can be computed in \((2+\delta)^{k}n^{O(1)}\) time for any constant \(\delta>0\), where \(k\) is the number of terminals. Moreover, under Gap-ETH no \((2-\varepsilon)\)-approximation can be computed in \(f(k)n^{O(1)}\) time for any \(\varepsilon>0\) and computable function \(f\)._A generalization of both Directed Steiner Tree and Strongly Connected Steiner Subgraph is the Directed Steiner Network problem [216], for which an edge-weighted directed graph is given together with a list of ordered terminal pairs. The aim is to compute the cheapest subgraph that contains a path from \(s\) to \(t\) for every terminal pair \((s,t)\). If \(k\) is the number of terminals, then for this problem no \(k^{1/4-o(1)}\)-approximation can be computed in \(f(k)n^{O(1)}\) time [59] for any computable function \(f\), under Gap-ETH. Both a PAS and a PSAKS exist [50] for the special case when the input graph is planar and bidirected, i.e., for every directed edge \(uv\) the reverse edge \(vu\) exists and has the same cost. Similar to the PSAKS for the Steiner Tree problem, these two algorithms are based on a generalization of Borchers and Du [199]. That is, Chitnis et al. [50] show that a planar solution in a bidirected graph can be covered by planar graphs with at most \(2^{O(1/\varepsilon)}\) terminals each, such that the sum of their costs is at most \(1+\varepsilon\) times the cost of the solution. These covering graphs may need to contain edges that are reverse to those in the solution, but are themselves not part of the solution. For this the underlying graph needs to be bidirected. Analogous to Steiner Tree, to obtain a kernel it then suffices to compute solutions for every possible list of ordered pairs of at most \(2^{O(1/\varepsilon)}\) terminals. In contrast to Steiner Tree however, there is no FPT algorithm for this. Instead, an XP algorithm with runtime \(2^{O(k^{3/2}\log k)}n^{O(\sqrt{k})}\) needs to be used, which runs in polynomial time for \(k\leq 2^{O(1/\varepsilon)}\) terminals with \(\varepsilon\) being a constant. After taking the union of all computed solutions, the number of Steiner vertices and the encoding length of the edge weights can be reduced in a similar way as for the Steiner Tree problem. To obtain a PAS, the algorithm will guess how the planar optimum can be covered by solutions involving only small numbers of terminals. It will then compute solutions on these subsets of at most \(2^{O(1/\varepsilon)}\) terminals using the same XP algorithm. **Theorem 30** ([50]). : _For the Directed Steiner Network problem on planar bidirected graphs a \((1+\varepsilon)\)-approximation can be computed in \(\max\{2^{k^{O(1/\varepsilon)}},n^{2^{O(1/\varepsilon)}}\}\) time for any \(\varepsilon>0\), where \(k\) is the number of terminals. Moreover, a \((1+\varepsilon)\)-approximate kernel of size \((k/\varepsilon)^{2^{O(1/\varepsilon)}}\) can be computed in polynomial time._