In general case |X|=3q, C={C_1,C_2,...,C_m},|C|=m. Question: Is there exists an exact cover C* of X with |C*|=q? And this problem is known to be NP-complete.

But, the restricted version of X3C problem where |C|<=2q. We refer this as X3C_2.

Is X3C_2 NP-complete?


marked as duplicate by D.W., Marzio De Biasi, Gamow, Bjørn Kjos-Hanssen Sep 2 at 23:36

This question was marked as an exact duplicate of an existing question.

  • 2
    $\begingroup$ Appears to be a duplicate of cstheory.stackexchange.com/q/44468/5038 $\endgroup$ – D.W. Sep 2 at 19:53
  • $\begingroup$ Perhaps it is homework. Why should otherwise the same exercise show up twice within a couple of days? $\endgroup$ – Gamow Sep 2 at 20:54