Consider the special case of the minimum set cover problem where each element of the universe occurs in at most 3 sets.
- Can this problem be solved in polynomial time?
- Is there a nontrivial upper bound on the cardinality of the minimum cover?
Forgive my ignorance. I'm not a computer scientist.