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$.

$\endgroup$
4
$\begingroup$

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

$\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.