Set cover problem with constant size subset Consider a variation of the set cover problem in which the size of the subsets is no larger than a constant $k$. Is this variation still NP-hard?
The problem is NP-hard for $k\ge3$. It has a straightforward reduction from the  3-dimensional matching problem.