1
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

The problem is NP-hard for $k\ge3$. It has a straightforward reduction from the 3-dimensional matching problem.

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Helium Jul 14 '14 at 19:36
  • 1
    $\begingroup$ @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. $\endgroup$ – Hendrik Jan Jul 20 '14 at 11:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.