NP Complete, The Graph Coloring Problem

Search Site map Contact us Operation Clog

Main Page

Languages

Complexity Theory

NP Complete Problems

Use the arrows

below to step through NP Problems.

Custom Links:

The Graph Coloring Problem

Given a graph, can we assign one of three colors (say red, blue, or green) to each vertex, such that no adjacent vertices have the same color?

This can be reduced to satisfiability, hence it is np complete.

Given a boolean expression, assign a vertex to each variable, and connect these vertices to a reference vertex g (colored green). Two other reference vertices are connected to g, and to each other. These will be colored red and blue, and are labeled r and b. Like reference voltages in electrical circuitry, these vertices will be connected to points throughout the graph.

Intermediate results such as x|(y&z) are represented by vertices, connected to g, hence they too are red or blue.

Treat red as true and blue as false, and tie the output of the entire boolean expression to b, whence it must be red. In other words, the boolean expression must come out true.

By demorgan's laws, it is enough to implement or and not. Not is easy; tie x and o to g, and to each other, and o (the output) is equal to ~x.

Now for the or gate, o = x|y. This gate requires three intermediate vertices; call them v₁ v₂ and v₃. Note, the intermediates are not all connected to g.

Connect v₁ to ~x and y, hence it cannot equal ~x or y. Remember that it could be green, and it must be green if x = y.

Connect v₂ to x, y, and v₁. If x and y are different then v₂ is green and v₁ = ~y. If x and y are the same then v₁ is green and v₂ = ~y.

Connect v₃ to v₂ and r. If x and y are different then v₃ is blue. If x and y are the same then v₃ could be green, or it could be blue if y is false.

connect the output o to g, v₂, and v₃. Verify that o = x|y.

Coloring graphs using n colors is no easier than 3 (no surprise there). For any boolean expression, construct a graph as above, and add n-3 vertices tied to each other and to everything else. The additional vertices take up the slack, consuming the extra colors, and preventing anyone else from using them.

A two color algorithm is straightforward. Start at any vertex and color it red. Color the adjacent vertices blue, then red, then blue, and so on throughout the graph. A collision of red and blue, as occurs in a pentagon, means the graph cannot be colored.

Planar Graphs

A planar graph can be colored using 5 colors in polynomial time. The proof provides the algorithm. I don't know if the 4 color theorem provides an efficient algorithm or not.

Custom Links: