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?

  • 7
    Your descriptio$n$ of "NP-complete" is not quite correct. Closer to the truth is this: problem is in NP if $a$$n$ alleged solutio$n$ 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.2012-03-27

2 Answers 2

13

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

  • 0
    @TsuyoshiIto Thanks, I've updated my answer accordingly.2012-03-28
4

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.

  • 1
    I don't think this is exactly an answer to the question.2016-08-12