# A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
## 4 Algorithms
### Faster Algorithms and Smaller Kernels via Approximation  
The focus of this section so far has been on problems for which its exact version is intractable (i.e., W[1]/W[2]-hard) and the goal is to obtain good approximations in FPT time. In this subsection, we shift our focus slightly by asking: does approximation allow us to find faster algorithms for problems already known to be in FPT? To illustrate this, let us consider Vertex Cover. It is of course well-known that the exact version of the problem can be solved in FPT time, with the current best running time being \(O^{*}(1.2738^{k})\)[271]. The question here would be: if we are allowed to output an \((1-\varepsilon)\)-approximate solution, instead of just an exact one, can we speed up the algorithm? To the best of our knowledge, such a question was tackled for the first time by Bourgeois et al. [272] and revisited quite a few times in the literature [273; 274; 20; 275; 276]. As one might have suspected, the answer to this question is a YES, as stated below. **Theorem 31** ([20]). : _Let \(\delta>0\) be such that there exists an \(O^{*}(\delta^{k})\)-time algorithm for Vertex Cover (e.g., \(\delta=1.2738\)). Then, for any \(\varepsilon>0\), there is an \((1+\varepsilon)\)-approximation for Vertex Cover that runs in \(O^{*}(\delta^{(1-\varepsilon)k})\) time._  
The main idea of the algorithm is inspired by the \"local ratio\" method in the approximation algorithms literature (see e.g., [277]) and we sketch it here. The algorithm works in two stages. In the first stage, we run the greedy algorithm: as long as we have picked less than \(2\varepsilon k\) vertices so far and not all edges are covered, pick an uncovered edge and add both endpoints to our solution. In the second stage, we run the exact algorithm on the remaining part of the graph to find a Vertex Cover of size \((1-\varepsilon)k\). Since the first stage runs in polynomial time, the running time of the entire algorithm is dominated by the second stage, whose running time is \(O^{*}(\delta^{(1-\varepsilon)k})\) as desired. The correctness of the algorithm follows from the fact that, for each selected edge in the first step, the optimal solution still needs to pick at least one endpoint. As a result, the optimal solution must pick at least \(\varepsilon k\) vertices with respect to the first stage (compared to \(2\varepsilon k\) picked by the algorithm). Thus, when the optimal solution is of size at most \(k\), there must be a solution in the second stage of size at most \((1-\varepsilon)k\), meaning that the algorithm finds such a solution and outputs a vertex cover of size \((1+\varepsilon)k\) as claimed. The above \"approximate a small fraction and brute force the rest\" approach of Fellows et al. [20] generalizes naturally to problems beyond Vertex Cover. Fellows et al. [20] formalized the method in terms of \(\alpha\)-fidelity kernelization and apply it to several problems, including Connected Vertex Cover, \(d\)-Hitting Set and Steiner Tree. For these problems, the method gives an \((1+\varepsilon)\)-approximation algorithm that runs in time \(O^{*}(\delta^{(1-\Omega(\varepsilon))k})\), where \(\delta>0\) denotes a constant for which a \(O^{*}(\delta^{k})\)-time algorithm is known for the exact version of the corresponding problem. The approach, in some form or another, is also applicable both to other parameterized problems [278; 279] and to non-parameterized problems (e.g., [272]); since the latter is out-of-scope for the survey, we will not discuss the specifics here. An intriguing question related to this line of work is whether it must be the case that the running time of \((1+\varepsilon)\)-approximation algorithms is of the form \(O^{*}(\delta^{(1-\Omega(\varepsilon))k})\). That is, can we get a \((1+o(1))\)-approximation for these problems in time \(O^{*}(\lambda^{k})\) where \(\lambda\) is a constant strictly smaller than \(\delta^{2}\) More specifically, we may ask the following:  
**Open Question 16**.