# A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
## 4 Algorithms
### Covering Problems
#### 4.2.1 Minimization Variants
For the second case, note that these vertices have degree at most \(\Delta\) and they have at most \(k\) false twins, meaning that there are at most \(k^{1+\Delta}=k^{1+1/\varepsilon}\) such vertices. In other words, the kernel is of size \(k^{O(1/\varepsilon)}\) as desired. This constitutes the main ideas in the proof; let us stress again that the actual proof is of course more complicated than this since we did not define rule (i) formally. Recently, Krithika et al. [131] considered the following structural parameters beyond the solution size: split deletion set, clique cover and cluster deletion set. In each case, the authors provide a PSAKS for the problem. We will not fully define these parameters here, but we note that the first parameter (split deletion set) is always no larger than the size of the minimum vertex cover of the graph. In another very recent work, Majumdar et al. [132] give a PSAKS for each of the following parameters, each of which is always no larger than the solution size: the deletion distance of the input graph to the class of cographs, the class of bounded treewidth graphs, and the class of all chordal graphs. Hence, these results may be viewed as a generalization of the aforementioned PSAKS from [18]. **Connected Dominating Set. ** Similar to Connected Vertex Cover, the Connected Dominating Set problem is the variant of Dominating Set for which the solution additionally needs to induce a connected subgraph of the input graph. When placing no restriction on the input graph, the problem is as hard to approximate as Dominating Set. However, for some special classes of graphs, PSAKS or bi-PSAKS [133] are known; these include graphs with bounded expansion, nowhere dense graphs, and \(d\)-biclique-free graphs [134]. **Covering Problems parameterized by Graph Width Parameters. ** Several works in literature also study the approximability of variants of Vertex Cover and Dominating Set parameterized by graph widths [105; 135]. These variants include:  
* Power Vertex Cover (PVC). Here, along with the input graph, each edge has an integer demand and we have to assign (power) values to vertices, such that each edge has at least one endpoint with a value at least its demand. The goal is to minimize the total assigned power. Note that this is generalizes of Vertex Cover, where edges have unit demands. * Capacitated Vertex Cover (CVC). The problem is similar to Vertex Cover, except that each vertex has a capacity which limits the number of edges that it can cover. Once again, Vertex Cover is a special case of CVC where each vertex's capacity is \(\infty\). * Capacitated Dominating Set (CDS). Analogous to CVC, this is a generalization of Dominating Set where each vertex has a capacity and it can only cover/dominate at most that many other vertices. All problems above are FPT under standard parameter (i.e., the optimum) [135; 136]. However, when parameterizing by the treewidth [137], all three problems become \(W[1]\)-hard [135]. (This is in contrast to Vertex Cover and Dominating Set, both of which admit straightforward dynamic programming FPT algorithms parameterized by treewidth.) Despite this, good FPT approximation algorithms are known for the problem. In particular, a PAS is known for PVC [135]. For CVC and CDS, a bicriteria PAS exists for the problem [105], which in this case computes a solution of size at most the optimum, so that no vertex capacity is violated by more than a factor of \(1+\varepsilon\). The approximation algorithms for CVC and CDS are results of a more general approach of Lampis [105]. The idea is to execute an \"approximate\" version of dynamic programming in tree decomposition instead of the exact version; this helps reduce the running time from \(n^{O(w)}\) to \((\log n/\varepsilon)^{O(w)}\), which is FPT. The approach is quite flexible: several approximation for graphs problems including covering problems can be achieved via this method and it also applies to clique-width. Please refer to [105] for more details.