1
$\begingroup$

Consider the following variant of set cover:

Given: Target set $T$ and a collection of sets $\mathcal{C}$, such that $T \subseteq \bigcup_{C \in \mathcal{C}} C$.

Wanted: A subset $\mathcal{C'}$ of $\mathcal{C}$, such that $T \subseteq \bigcup_{C \in \cal{C'}} C$ and $|\bigcup_{C \in \cal{C'}} C|$ is minimal.

In other words, we are looking for a covering of $T$ that covers as few additional elements as possible.

It is relatively easy to see that this problem is NP-complete.

Is this a known problem? What is its name?

Improve this question
$\endgroup$
2
  • $\begingroup$ One of the standard generalizations of Set Cover is minimizing a linear function subject to a submodular constraint. See e.g. algnotes.info/on/background/set-cover-wolsey . Doesn't look like it quite captures your problem though. $\endgroup$
    – Neal Young
    Nov 8 at 20:42
  • $\begingroup$ Ouch, indeed the $\sum$'s should be $\bigcup$'s. $\endgroup$
    – Jan Reineke
    Nov 8 at 21:29

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.