Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
3  
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. –  Gerry Myerson Mar 27 '12 at 22:51
add comment

1 Answer

up vote 6 down vote accepted

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

share|improve this answer
    
You are talking about coloring of a planar graph, but strictly speaking, the question is about coloring of a general graph. –  Tsuyoshi Ito Mar 27 '12 at 23:53
    
@TsuyoshiIto Thanks, I've updated my answer accordingly. –  Slaviks Mar 28 '12 at 6:17
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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