1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

Hence, there is no known method that is essentially better than "try every possibility".

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you very much! I suspected it is NP-hard, but wasn't sure. $\endgroup$ – Przemek Apr 25 '17 at 14:02
  • $\begingroup$ And could you provide a little bit more information? How it exactly translate into this problem? $\endgroup$ – Przemek Apr 25 '17 at 14:17
0
$\begingroup$

Could someone explain the way that Mees de Vries answer meets my criteria. I think it is about searching smallest number of subsets covering SET, not about finding vertices that satisfy the maximum number of subsets. Correct me if I am wrong.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.