1
$\begingroup$

The 3-COLOR problem takes as input a graph and decides whether it can be colored using only 3 colors so that no 2 adjacent nodes have the same color.

The reduction from 3-SAT to 3-COLOR uses the following gadget (see below) to represent a clause in the 3-SAT formula.

It is clear that a valid 3-coloring exists only when at least one of x, y, or z has the same color as T. Now, suppose all 3 literals are False. Then, if the x, y and z nodes are colored the same as the F node, there is no valid 3-coloring.

However, to the 3-color algorithm, the gadget is just a subgraph. Even if x, y and z are False, if we color them the same as the T node, there would be a valid coloring. It's not clear to me that you can specify in the input to the 3-color algorithm that if a literal is False/True, it should have the same color as F/T.

So, how is the reduction valid?

enter image description here

$\endgroup$
1
$\begingroup$

Actually, there is no 3-coloring if the 3 literals are colored as F. This is because the node after the "merge" will be colored as F, while the blank below left of T will be as X. The remaining node (upper left of T) can have no valid color in this case.

$\endgroup$
  • $\begingroup$ it's true that if the 3 literals have the same color as F there can be no valid 3-coloring. My question was, given that the 3 literals are False, why couldn't the 3-color algorithm simply color the 3 literal nodes the same as T, in which case we have a valid 3-coloring. $\endgroup$ – user137481 Dec 1 '14 at 22:21
  • $\begingroup$ the point is that you have to choose an asignment for all literals: x cannot be colored true in a clause and false in an other. If the 3 literals are false and this is a valid asignment, then there is no problem. $\endgroup$ – Denis Dec 1 '14 at 22:41
  • $\begingroup$ OK, I've got it now. Thanks! $\endgroup$ – user137481 Dec 2 '14 at 18:36
1
$\begingroup$

For each variable y, build two vertices, one for y and one for ~y. Connect both y and ~y to X, the unique global node that is connected in a triangle with T(rue) and F(alse). These connections will ensure that one of {y,~y} gets a color of T and the other gets a color of F. This is what gives you the connection between a coloring and a truth assignment.

Then you use the gadget to connect each clause in the 3-SAT formula, using the right literal vertices. Each gadget connects to the same global T as shown in the picture.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.