3
$\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
    Commented Nov 8, 2023 at 20:42
  • $\begingroup$ Ouch, indeed the $\sum$'s should be $\bigcup$'s. $\endgroup$
    – Jan Reineke
    Commented Nov 8, 2023 at 21:29

1 Answer 1

Reset to default
3
$\begingroup$

We can abstract this problem as submodular minimization (minimize additional covers) under submodular cover (set cover) constraint. I'll point you towards two papers in this area.

The first paper proves that a primal-dual algorithm achieves constant approximation if maximum frequency is fixed. The second paper gives a more careful bound.

Improve this answer
$\endgroup$
1
  • $\begingroup$ The Iwata and Nagano paper proves a strong lower bound on the approximation when the maximum frequency is not bounded. The lower bound should probably hold for the OPs problem as well. $\endgroup$
    – Chandra Chekuri
    Commented Dec 4, 2023 at 0:46

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.