# A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
## 4 Algorithms
### Covering Problems
#### 4.2.3 Other Related Problems  
There are several other covering-related problems that do not fall into the two categories we discussed so far. We discuss a couple such problems below.  
Min \(k\)-Uncovered.The first is the Min \(k\)-Uncovered problem, where the input is a set system and we would like to select \(k\) sets as to minimize the number of uncovered elements. When we are concerned with exact solutions, this is of course the Set Cover. However, the optimization version becomes quite different from Max \(k\)-Coverage. In particular, since it is hard to determine whether we can find \(k\) subsets that cover the whole universe, the problem is not approximable at all in the general case. However, if restrict ourselves to graphs and hypergraphs (for which we refer to the problem as Min \(k\)-Vertex Cover), it is possible to get a (randomized) PAS for the problem [146]:  
**Theorem 21** ([146]).: _For the Min \(k\)-Vertex Uncovered problem in \(d\)-uniform hypergraphs, a \((1+\varepsilon)\)-approximation can be computed in \(O^{*}\left((d/\varepsilon)^{k}\right)\) time for any \(\varepsilon>0\)._  
The algorithm is based on the following simple randomized branching: pick a random uncovered element and branch on all possibilities of selecting a subset that contains it. Notice that since an element belongs to only \(d\) subsets, the branching factor is at most \(d\). The key intuition in the approximation proof is that, when the number of elements we have covered so far is still much less than that in the optimal solution, there is a relatively large probability (i.e., \(\varepsilon\)) that the random element is covered in the optimal solution. If we always pick such a \"good\" element in most branching steps, then we would end up with a solution close to the optimum. Skowron and Faliszewski [146] formalizes this intuition by showing that the algorithm outputs an \((1+\varepsilon)\)-approximate solution with probability roughly \(\varepsilon^{k}\). Hence, by repeating the algorithm \((1/\varepsilon)^{k}\) time, one arrives at the claimed PAS. To the best of our knowledge, it is unknown whether a PSAKS exists for the problem.  
Min \(k\)-Coverage.Another variant of the Set Cover problem studied is Min \(k\)-Coverage [150; 151; 152], where we would like to select \(k\) subsets that minimizes the number of covered elements. We stress here that this problem is not a relaxation of Set Cover but rather is much more closely related to graph expansion problems (see [151]).  
It is known that, when there is no restriction on the input set system, the problem is (up to a polynomial factor) as hard to approximate as the Densest \(k\)-Subgraph problem [150]. Hence, by the inapproximability of the latter discussed earlier in the survey (Theorem 8), we also have that there is no \(k^{o(1)}\)-approximation algorithm for the problem that runs in FPT time.  
Once again, the special case that has been studied in literature is when the input set system is a graph, in which case we refer to the problem as Min \(k\)-Vertex Cover. Gupta, Lee, and Li [153; 154] used the technique of Marx [8] to give a PAS for the problem with running time \(O^{*}((k/\varepsilon)^{O(k)})\). The running time was later improved in [147] to \(O^{*}((1/\varepsilon)^{O(k)})\). The algorithm there is again based on branching, but the rules are more delicate and we will not discuss them here. An interesting aspect to note here is that, while both Max \(k\)-Vertex Cover and Min \(k\)-Vertex Cover have PSAKS of the (asymptotically) same running time, the former admits a PSAKS whereas the latter does not (assuming a variant of the Small Set Expansion Conjecture) [147].  
To the best of our knowledge, Min \(k\)-Vertex Cover has not been explicitly studied on \(d\)-uniform hypergraphs before, but we suspect that the above results should carry over from graphs to hypergraphs as well.