NP complete

[soultrav]

Given the problem:
"Can a graph's G(V,E) vertices be colored using k colors such that for every edge (u,v) of the graph, color(u) != color(v) ?"
, can it be solved in deterministic polynomial time?
I found http://www.geocities.com/krishnapg/graphcoloring.html , which states that solves the problem in polynomial time, but I also read that this problem is NP-complete...could the both of them be true? Any help appreciated, thanks.

[Zachm]

Caution !
The algorithm described at the provided link DOES NOT solve the Graph k-Coloring for the general case. It may work for some graphs but perform very poorly on others. The algorithm described will find A coloring of the graph but not necessarily the optimal coloring (with minimum number of colors).

You can try and think of graph input examples where the algorithm will perform poorly (usually very simple examples are sufficient).

Regards,
Zachm

EDIT:
Attached an example of such a "bad example" graph - a bipartite graph where each vertex is connected to all vertices of the other side except the vertex directly in front of it. All vertices have the same degree so the proposed algorithm might color vertex 1 with color 1, then it won't be able to color any vertex on the other side except 1' so it might color 1'. At this point the algorithm must use color #2 so in the same manner it might color vertices 2 and 2' with it and will be forced to use a 3rd color. In fact, the number of colors the algorithm might use is O(n) for this type of graph, where in fact 2 colors will suffice.
See attached image.

[TheCPUWizard]

Zachm pointed out a key "feature" of this problem, and that is the necessity to use the minimul number of colors. Without this requirement, the problem is (relatively) trivial, yet with it, it becomes much more complex.

The the "solvability" characteristics can not even be discussed into this is taken into account.

[soultrav]

Thank you for the remark ... but to my shame I only know see that the problem stated in the link is a problem of optimization , and my problem is one of decision ("Can a graph's G(V,E) vertices be colored using k colors such that for every edge (u,v) of the graph, color(u) != color(v) ?") .
Could this decision problem be solved better than with backtracking?

Regards

[Zachm]

Note that for the Graph k-coloring problem, the following 2 statements are true:

1. If you can solve the decision problem in polynomial time then you are also able to solve the Graph k-Coloring optimization problem in polynomial time.
For Graph k-coloring, just run your polynomial time decision algorithm n times for k=1..n, n being the number of vertices in the graph, and return the minimal k for which the decision algorithm returns true.

2. If you can solve the omptimization problem in polynomial time then you are also able to solve the decision problem in polynomial time.
For Graph k-coloring, just run your polynomial time optimization algorithm and count the number of colors produced. If it is <=k then return true, otherwise return false.

The conclusion: if indeed the guy that wrote the algorithm at the provided link would have solved the optimization algorithm in polynomial time, he would've also solved the decision problem in polynomial time. Gladly (or sadly ?) he didn't solve it, rather found an approximation of it (and one bad O(n) ratio approximation).

Regards,
Zachm

[soultrav]

Yes, you're right ... thanks for the tips :-)