suppose we have a finite set X and a set S of subsets of X and we want to determine is there a subset S' of S such that all members of X belong to exactly one set in S' I think the best problem to reduce to this problem is 3-colorable graph and i think X is the set of vertices.But i can't find the best rule for creating set S from G. is there any idea?
4
-
$\begingroup$ Where does this problem come from? Are you looking for an (implementable) algorithm, a solution to a single problem or something else? Why do you think the problem can be reduced to a 3-coloring problem? $\endgroup$– Joonas IlmavirtaCommented Nov 21, 2014 at 14:05
-
$\begingroup$ I want to prove that this problem is NP-complete and I guess 3-colorable graph problem is similar to it maybe not.i'm not sure $\endgroup$– amir veysehCommented Nov 21, 2014 at 14:14
-
$\begingroup$ I don't think it's a good idea to use the set of vertices of the graph as the X in your problem. The input to 3-coloring (namely the graph) is only polynomially larger than the set of vertices, but the input to your question, including the family S, could be exponentially larger than X. So "PTime" for your problem could be exponential time relative to the size of X. $\endgroup$– Andreas BlassCommented Nov 21, 2014 at 15:08
-
$\begingroup$ @AndreasBlass yes i agree with you,I've tried so many ways to produce S from X by G and its edges but all of them failed.really I don't have any idea to how prove it after several hours of thinking about it $\endgroup$– amir veysehCommented Nov 21, 2014 at 15:22
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
This problem is indeed NP-complete and was in fact one of Karp's 21 NP-complete problems. Googling exact cover will lead to enlightenment.
answered Nov 21, 2014 at 19:44