Graph Three Coloring

The GraphThreeColoring problem is basically this:

Here's a graph. Using only three colors, can you color the vertices such that adjacent vertices have different colors?

This problem is NpComplete, and on this page I'll give an outline of the proof.

Firstly, let's call our colors 0, 1 and *. Here's a graph to color:

It's easy to color - that's not the point at this stage.

The first thing to notice is that the top three vertices must all get different colors because they are mutually joined. We can start our coloring, then, by fixing their colors to be 0, 1 and * in that order, like this:

By using the trick of having a triangle somewhere and forcing its colors we can force other vertices to be, or not to be, various things. For example, the two vertices at the bottom are now forced to be digits. They can't be * because they are joined to the vertex labelled *. This trick means that we can draw graphs to be three colored and put in them vertices that are already forced. The simple way of drawing that second graph would then be this:

Now the interesting thing about this graph is that the vertex on the left has to be a digit, the vertex on the right has to be a digit, and they have to be different. This is a binary Not gate.

TheInterestedReader may choose to confirm that the following graph is a logical And function.

By symmetry, exchanging the 0 and 1 gives us a logical Or function.

We can now create any logical function we choose by stringing together these graphs, having the output vertex of one be the same vertex as the input vertex of one or more others. We can even create a graph that will multiply two binary numbers together, or one that acts as a TuringMachine. To do that we create a graph that can represent the current state, duplicate it as many times as we require steps for the computation, and then connect each graph to the next with the logic that converts this state into the next state.

So, how do we prove that GraphThreeColoring is NpComplete?

Take any NP problem. We want to show that under the assumption that we can three-color any graph in unit time, we can solve the given NP problem in polynomial time.

It's more-or-less true that, because the problem is NP, there is a polynomial-time process that takes the problem and a purported solution, and checks whether it really is a solution. It's also more-or-less true that this checking process can be encoded in a TuringMachine.

Build the graph that corresponds to this specific TuringMachine. When you force the colorings on the input nodes and then color the graph, the output node will be colored 1 for Yes, this is a solution or 0 for No, this is not a solution.

Leave the input nodes corresponding to the purported solution unforced, force the output to be 1, and now make use of our assumption and color it. This, under our assumption, takes unit time, and will give us a coloring of the input nodes from which we can read out our solution. Thus we have solved the original problem.

Is it in polynomial time? Only if the graph is polynomial in the size of the problem, which requires checking but is in fact true.

So that's an outline of a proof. Convinced? Maybe not. There are a lot of details to check, and actually understanding the processes involved is tricky, but it's pretty much all there.

Comments welcome.

It seems to me that you reduce CircuitSatisfiability? to GraphThreeColoring. I would first show the NpCompleteness of the first, and then explicitly give the reduction.

The purpose of this page is to show NpCompleteness of a problem - that's the hard bit. Showing equivalence is then fairly easy. Your suggested path is certainly one way to show NpCompleteness of Three Coloring, but the method given here is direct and complete, and therefore perhaps more enlightening.

Also, the and gate and the not gate are sufficient to get any circuit, so it's unnecessary to implement the or gate (directly).

True, and most people here will know that. The FullAdder graph can be synthesized from these gates too, but there is a much smaller graph that accomplished the same end. These were examples to show the principles, and as such the comment about the Or gate has its place.

And ThankYou for the comments - they are helpful.

MarkJasonDominus demonstrated a polynomial-time reduction from GraphThreeColoring to PerlLanguage RegularExpression matching (using BackReferences?):

http://perl.plover.com/NPC/NPC-3COL.html

-- GregBacon