8
$\begingroup$

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?

$\endgroup$
  • 7
    $\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 Myerson Mar 27 '12 at 22:51
13
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ You are talking about coloring of a planar graph, but strictly speaking, the question is about coloring of a general graph. $\endgroup$ – Tsuyoshi Ito Mar 27 '12 at 23:53
  • $\begingroup$ @TsuyoshiIto Thanks, I've updated my answer accordingly. $\endgroup$ – Slava Kashcheyevs Mar 28 '12 at 6:17
4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I don't think this is exactly an answer to the question. $\endgroup$ – 6005 Aug 12 '16 at 4:38

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.