2
$\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$
1

1 Answer 1

4
$\begingroup$

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

$\endgroup$
2
  • 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, 2014 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$ Jul 20, 2014 at 11:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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