patternMinor
Help reducing 3-SAT to 3-COLORING
Viewed 0 times
satcoloringhelpreducing
Problem
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:
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?
"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 RBut 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?
Solution
I believe the goal of this construction is to try to assign true or false to each variable. The color assigned to x will determine whether it's true or false, and there's an edge from x to ¬x to ensure that each variable and its negation get different values. The edge from each variable to R ensures that there are only two possible colors that can be assigned to x, one of which means true and one of which meand false.
Hope this helps!
Hope this helps!
Context
StackExchange Computer Science Q#19040, answer score: 8
Revisions (0)
No revisions yet.