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 '21 at 7:22

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.