Help reducing 3-SAT to 3-COLORING
-
30-10-2019 - |
Pergunta
I am working on showing that 3-colorability is NP-complete. I read a few articles and walkthroughs on this but none are really clicking. I get to this part
"Then for every variable xi that appears in the instance of Satisfiability, we connect a vertex xi to a vertex xi, and we connect both xi and xi to red. This is illustrated below for a case where there are (only) 3 variables."
I think what they mean is something like this:
x1----x1* x2----x2* x3----x3*
\ / \ / \ /
\ / \ / \ /
R R R
But my question is, what exactly is this step doing?
With a little bit more thought, is this step just showing that given xi to be one color, then xi* has to be another, but also cannot be R, as they are both connected to it?
Nenhuma solução correta
Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange