0
$\begingroup$

Consider the special case of the minimum set cover problem where each element of the universe occurs in at most 3 sets.

  1. Can this problem be solved in polynomial time?
  2. Is there a nontrivial upper bound on the cardinality of the minimum cover?

Forgive my ignorance. I'm not a computer scientist.

Improve this question
$\endgroup$
1
  • 5
    $\begingroup$ The problem is already hard even with each element appearing in exactly 2 sets. For a min vertex cover instance with graph $G=(V,E)$, you can view it as a min set cover instance with one element for each edge $e \in E$, and one set for each vertex $v \in V$, with $e \in v$ if $v$ is an endpoint of $e$. $\endgroup$
    – Yonatan N
    Oct 12, 2021 at 7:22

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.