# A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
## 4 Algorithms
### Faster Algorithms and Smaller Kernels via Approximation
: _Let \(\delta>0\) be the smallest (known) constant such that an \(O^{*}(\delta^{k})\)-time exact algorithm exists for Vertex Cover. Is there an algorithm that, for any \(\varepsilon>0\), runs in time \(f(1/\varepsilon)\cdot O^{*}(\lambda^{k})\) for some constant \(\lambda<\delta\)?_  
Of course, the question applies not only for Vertex Cover but other problems in the list as well. The informal crux of this question is whether, in the regime of very good approximation factors (i.e. \(1+o(1)\)), approximation can still be exploited in such a way that the algorithm works significantly better than the approach \"approximate a \(o(1)\) fraction and then brute force\". Turning back once again to our running example of Vertex Cover, it turns out that algorithms faster than \"approximate a small fraction and then brute force\" are known [273; 275; 276] but only for the regime of large approximation ratios. In particular, Brankovic and Fernau [273] give faster algorithms than in Theorem 31 already for approximation ratios as small as \(3/2\). The algorithms in [275; 276] focus on the case of \"barely non-trivial\" \((2-\rho)\)-approximation factors. (Recall the greedy algorithm yields a 2-approximation and, under the Unique Games Conjecture, the problem is NP-hard to approximate to within any constant factor less than 2.) The algorithm in [275] has a running time of \(O^{*}(2^{k/2^{\Omega(1/\rho)}})\), which was later improved in [276] to \(O^{*}(2^{k/2^{\Omega(1/\rho^{2})}})\). These running times should be contrasted with that of \"approximate a small fraction and then brute force\" (i.e., applying Theorem 31 directly with \(\varepsilon=1-\rho\)) which gives an algorithm with running time \(O^{*}(2^{k\rho})\). In other words, Refs. [275; 276] improve the \"saving factor\" from \(1/\rho\) to \(2^{\Omega(1/\rho)}\) and \(2^{\Omega(1/\rho^{2})}\) respectively. It should be noted however that, since the known \((2-o(1))\)-factor hardness of approximation is shown via the Unique Games Conjecture and unique games admit subexponential time algorithms [280; 281], it is still entirely possible that this regime of approximating Vertex Cover admits subexponential time algorithms as well. This is perhaps the biggest open question in the \"barely non-trivial\" approximation range:  
**Open Question 17**. : _Is there an algorithm that runs in \(2^{o(k)}n^{O(1)}\) time and achieves an approximation ratio of \((2-\rho)\) for some absolute constant \(\rho>0\)?_  
Let us now briefly discuss the techniques used in some of the aforementioned works. The algorithms in [273; 275] are based on branching in conjunction with certain approximation techniques. (See also [282] where a similar technique is used for a related problem Total Vertex Cover.) A key idea in [273; 275] is that (i) if the (average or maximum) degree of the graph is small, then good polynomial-time approximation algorithms are known [283] and (ii) if the degree is large, then branching algorithms are naturally already fast. The second part of [273] involves a delicate branching rule. However, for [275], it is quite simple: for some threshold \(d\) (to be specified), as long as there exists a vertex with degree at least \(d\), then (1) with some probability, simply add the vertex to the vertex cover, or (2) branch on both possibilities of it being inside the cover and outside. After this branching finishes and we are left with low-degree graphs, just run the known polynomial-time approximation algorithms [283] on these graphs. The point here is that the \"error\" incurred if option (1) is chosen will be absorbed by the approximation. By carefully selecting \(d\) and the probability, one can arrive at the desired running time and approximation guarantee. This algorithm is randomized, but can be derandomized using the sparsification lemma [284]. To the best of our knowledge, this \"barely non-trivial approximation\" regime has not been studied beyond Vertex Cover. In particular, while Bansal et al.