# Maximize number of covered sets by choosing given number of elements

I am not sure if it's a known probem:

There is a set of some elements. For the purpose of this explanation that can be a subset of natural numbers, let's say $\{1, 2, ..., 20\}$. Let's call it $SET$.

There are also given subsets of the $SET$. That subsets don't have to be disjoint and sum of them doesn't have to cover the $SET$ (i.e. $\{1, 3, 5\}$, $\{8, 9, 14\}$, $\{1, 10, 15, 18, 20\}$, $\{5, 6, 8, 9\}$, and so).

Now, with given number $k$ ($0<k<|SET|$), how to choose $k$ elements of the $SET$ to maximize number of covered (by choosen elements) subsets.

Thank you for help, Przemek.

This problem is NP-hard (and in fact NP-complete): if you can solve this problem efficiently, you can efficiently solve the minimum vertex cover problem. Namely, given a graph $G = (V,E)$, let $\mathrm{SET} = V$, the set of vertices. As subsets take, for each vertex $v \in V$, the set containing $v$ and all neighbours of $v$. Then the minimal vertex cover size is the least $k$ such that $k$ of the subsets cover the entire vertex set.