2
$\begingroup$

The decision version of the 3-COLOR problem is the problem of deciding whether an input graph G(V, E) can be colored using only 3 colors so that no 2 adjacent vertices have the same color.

I had interpreted that to mean that we were looking for any coloring.

However, most proofs I have seen that reduce 3-SAT to 3-COLOR to prove that 3-SAT is NP-Complete use subgraph "gadgets" where some of the nodes are already colored.
But in this case, it would only show that a specific 3-coloring (i.e. some nodes on the input graph are pre-colored) does not exist.

It doesn't show that no 3-coloring exists. Can someone clarify why the reduction is valid?

$\endgroup$
3
$\begingroup$

An important part of these gadget schemes is that there is a 3-clique somewhere called the palette that arbitrates the logic roles of colors. In other words, there are 3 nodes all connected to each other, labeled $v_T$, $v_F$, and $v_R$. The palette can be arbitrarily colored, and whatever colors are chosen represent the 3 logic values. Then when a gadget has a fixed "true" node in it, arcs are extended from fixed $v_F$ and $v_R$ nodes to it, to compel its color to be the same as $v_T$.

So the reduction doesn't require any strange modifications to the concept of the 3-COL problem. The reduction algorithm generates a planar graph, and that graph can be 3-colored iff the 3-SAT problem can be satisified.

$\endgroup$
  • $\begingroup$ The fixed "true" node is where I'm having a problem. This means that the input graph to 3-COLOR has a node that is pre-colored "true". If answer returned is "No", it means no coloring exists where the fixed node is colored "true". It does not necessarily mean that no 3-coloring exists. For example, a coloring could exist where the fixed node was colored either "False" or "Base". $\endgroup$ – user137481 Nov 21 '14 at 16:04
  • $\begingroup$ No, no colors are fixed. "$v_T$" is just a label on a node. Arcs are added so that other nodes are forced to be the same color as it, and can also be labeled "$v_T$". It is easy to prove then that all $v_T$ nodes must be the same color, not that they must be a particular color. $\endgroup$ – NovaDenizen Nov 21 '14 at 16:55
1
$\begingroup$

To understand the proof, we must remember that in an unsatisfiable 3CNF formula it is impossible for all the clauses to be false at the same time and therefore they can not be colored with the same color. The only case where the clauses have the same truth value is when the formula is satisfiable. In this case all the clauses are true. In other words, if we can color the outputs of all the gadgets with the same color (whatever that color is), the formula 3CNF is necessarily satisfiable

$\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.