# Bounded-Frequency Minimum Set Cover Problem

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.

• 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$. Oct 12, 2021 at 7:22