# A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
## 4 Algorithms
### Covering Problems
#### 4.2.1 Minimization Variants  
We start out discussion with the minimization variants. For brevity, we overload the problem name and use the same name for the minimization variant (e.g., we use Set Cover instead of the more cumbersome Min Set Cover). Later on, we will use different names for the maximization versions; hence, there will be no confusion. Set Cover, Dominating Set and Vertex CoverAs discussed in detail in Section 3.1.2, Set Cover and equivalently Dominating Set are very hard to approximate in the general case. Hence, special cases where some constraints are placed on the set system are often considered. Arguably the most well-studied special case of Set Cover is the Vertex Cover problem, in which the set system is a graph. That is, we would like to find the smallest set of vertices such that every edge has at least one endpoint in the selected set (i.e., the edge is \"covered\"). Vertex Cover is well known to be FPT [126] and admit a linear-size kernel [127]. A generalization of Vertex Cover on \(d\)-uniform hypergraph, where the input is now a hypergraph and the goal is to find the smallest set of vertices such that every hyperedge contain at least one vertex from the set, is also often referred to as \(d\)-Hitting Set in the parameterized complexity community. However, we will mostly use the nomenclature Vertex Cover on \(d\)-uniform hypergraph because many algorithms generalizes well from Vertex Cover in graphs to hypergraphs. Indeed, branching algorithms for Vertex Cover on graphs can be easily generalized to hypergraphs, and hence the latter is also FPT. Polynomial-size kernels are also known for Vertex Cover on \(d\)-uniform hypergraphs [128]. While Vertex Cover both on graphs and \(d\)-uniform hypergraphs are already tractable, approximation can still help make algorithms even faster and kernels even smaller. We defer this discussion to Section 4.7. Connected Vertex CoverA popular variant of Vertex Cover that is the Connected Vertex Cover problem, for which the computed solution is required to induce a connected subgraph of the input. Just as Vertex Cover, the problem is FPT [129]. However, unlike Vertex Cover, Connected Vertex Cover does not admit a polynomial-time kernel [130], unless NP\(\subseteq\)coNP/poly. In spite of this, a PSAKS for Connected Vertex Cover exists:  
**Theorem 19** ([18]). : _For any \(\varepsilon>0\), an \((1+\varepsilon)\)-approximate kernel with \(k^{O(1/\varepsilon)}\) vertices can be computed in polynomial time._  
The ideas behind [18] is quite neat and we sketch it here. There are two reduction rules: (i) if there exists a vertex with degree more than \(\Delta:=1/\varepsilon\) just \"select\" the vertex and (ii) if we see a vertex with more than \(k\) false twins, i.e., vertices with the same set of neighbors, then we simply remove it from the graph. An important observation for (i) is that, since we have to either pick the vertex or all \(\geq\Delta\) neighbors anyway, we might as well just select it even in the second case because it affects the size of the solution by a factor of at most \(\frac{1+\Delta}{\Delta}=1+\varepsilon\). For (ii), it is not hard to see that we either select one of the false twins or all of them; hence, if a vertex has more than \(k\) false twins, then it surely cannot be in the optimal solution. Roughly speaking, these two observations show that this is an \((1+\varepsilon)\)-kernel. Of course, in the actual proof, \"selecting\" a vertex needs to be defined more carefully, but we will not do it here. Nonetheless, imagine the end step when we cannot apply these two reduction rules anymore. Essentially speaking, we end up with a graph where some (less than \((1+\varepsilon)k\)) vertices are marked as \"selected\" and the remaining vertices have degree at most \(\Delta\). Now, every vertex is either inside the solution, or all of its neighbors must lie in the solution. There are only (at most) \(k\) vertices in the first case.