6
$\begingroup$

Suppose $C_1, \ldots, C_m$ are subsets of $\{1, \ldots, n\}$. The goal is to find the smallest subcollection of $C_1, ..., C_m$ such that each element of $\{1, \ldots, n\}$ appears at least $k$ times in this subcollection.

If $k=1$, this is set cover. I would be interested to learn how to prove NP-hardness for $k=2$ and $k=3$.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

Hine: Given an instance of set cover, add $k-1$ copies of the set $\{1,\ldots,n\}$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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