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?

  • $\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$ Nov 8 at 21:29


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.