An NP-Complete problem can be checked efficiently, but has no known way of being solved in polynomial time.
Then, how is the graph coloring problem (http://en.wikipedia.org/wiki/Graph_coloring_problem) NP-Complete? How does one easily check it?
$\begingroup$
$\endgroup$
1
-
8$\begingroup$ Your description of "NP-complete" is not quite correct. Closer to the truth is this: problem is in NP if an alleged solution can be checked efficiently; it is NP-complete if every problem in NP can be reduced to it efficiently. The big question is whether every problem in NP can be solved in polynomial time, but there are questions (like integer factorization) for which we know neither whether they are NP-complete nor whether they can be solved in polynomial time. $\endgroup$– Gerry MyersonMar 27, 2012 at 22:51
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
For a check, you are given with a particular coloring of the given map. You just go through all the patches, check that the neighbors are of different color, and finally count the total number of colors. This algorithm scales linearly with the number of regions, so it is a polynomial check.
UPDATE: For a general graph (not necessarily planar) this algorithm will be at most quadratic in the number of vertices (colored regions).
answered Mar 27, 2012 at 17:55
-
$\begingroup$ You are talking about coloring of a planar graph, but strictly speaking, the question is about coloring of a general graph. $\endgroup$ Mar 27, 2012 at 23:53
-
$\begingroup$ @TsuyoshiIto Thanks, I've updated my answer accordingly. $\endgroup$ Mar 28, 2012 at 6:17
$\begingroup$
$\endgroup$
1
The Graph Coloring decision problem is np-complete, i.e, asking for existence of a coloring with less than 'q' colors, as given a coloring , it can be easily checked in polynomial time, whether or not it uses less than 'q' colors.
On the other hand the Graph Coloring Optimisation problem, which aims to find the coloring with minimum colors is np-hard, because even if you are given a coloring, you will not be able to say that it's minimum or not. This is the basic difference b/w np-complete and np-hard, and is applicable to many other problems as well, such as the Travelling Salesman Problem.
-
3$\begingroup$ I don't think this is exactly an answer to the question. $\endgroup$ Aug 12, 2016 at 4:38