November 2nd, 2011, 08:58 AM
P=NP? (polynomial graph coloring)
I came up with a polynomial bounded algorithm (exponential to be specific) for graph coloring a year or two ago. Does anyone agree/disagree with my findings? Here is my doc:
Polynomial time (tractable) algorithm for solving graph coloring:
Given a sequence of “colors” we will visit each node of the graph. Upon visiting that node we will check the colors of each neighbor node and set the color of the current node to the “lowest” color which is different from all neighbor nodes (all nodes are initialized to null). Continue until all nodes have been colored. The number of colors used is the minimum number of colors required.
Lowest = earliest color in the sequence
This solution is O(n^2): We must visit each node and all of its neighbors. For a fully connected graph this is n^2 iterations.
Proof of correctness:
Assume that there was 1 less color that could be used in the graph. Removing this color would require it to be replaced by another color. Because we select the lowest color not currently being used by any neighbor node, we must select a larger color (later in sequence) to replace it.
This introduces three possibilities:
1) The eliminated color still exists in the graph and it is replaced with another color that exists in the graph (no loss in colors)
2) The eliminated color no longer exists in the graph and it is replaced with another color that did not exist in the graph (no loss in colors)
3) The eliminated color still exists in the graph and it is replaced with another that did not exist in the graph (color gain)
None of these possibilities reduce the number of colors required.
It is impossible that the eliminated color no longer exists in the graph and it is replaced with another color that does exist in the graph (loss of a color). This is because every node is colored with the lowest possible color in the sequence, for another higher color to exist in the graph, it must be either:
1) connected another node of this sequence number (meaning this a node of this color still exists in the graph)
2) connected to this node (meaning we can not select it and thus must choose another higher color)
- A higher color will have the same issue
It is there for impossible to color the graph with fewer colors. This solves the NP-Complete problem of graph coloring in polynomial time.
… In code we could keep track of the color sequence in a bit map .. traversing this bit map for every node to select the smallest color in the sequence would add at most n to the complexity O(n^2 + n) = O(n^2)
Tags for this Thread
Click Here to Expand Forum to Full Width
This is a CodeGuru survey question.