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
scroll top