# 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.
• Thanks Hendrik. This is more like a hint than an answer. Could you please elaborate more on this so I can accept your answer? My understanding is that the problem is NP-hard for $k \ge 3$ (easy reduction from 3d matching) but not for $k=1$ or $k=2$, right? Jul 14, 2014 at 19:36
• @Mohsen Sure, it was a hint. Reading your comment it set you in the right direction. Just a hint, for two reasons. (1) If this is homework I like to help without spoiling all. (2) For myself I did not work out all details: e.g., is it necessary to consider the $|X|=|Y|=|Z|$ case and "exact cover" (see wikipedia)? Also $k=2$ is interesting. Most problems related to "matching" seem to be polynomially solvable as far as I consulted wikipedia. Again I did not check the precise formulation. Jul 20, 2014 at 11:13