Given k kinds of colors and a Graph G=(V,E), color each vertice. Decide whether there is a way that no two adjcent vertices have the same color(Which means it's proper).
K-sat Problem
Given K variables from X1 to Xk, and given a CNF in which each clause has only those k boolean variables.
k-sat( In The Nature of Computation )
Input: A CNF Boolean formula $\phi$ ,where each clause contains k variables
Question: Is $\phi$ satisfiable?
Reduce 3-sat to Coloring
Since these two problems are both condition constraints problems, it's useful to consider whether we could reduce one to another.
Here's how it works:
For the variables, we could create 2 vertices to map these varibles and for the operators,such as logical and logical or, we could use some small gadgets to realize their function.
Then, choose three colors used to map Boolean truth assignments. One for true, one for false and one for logical consistency, called auxiliary color.
Basically, we use edges to ensure that the relationship between colorability and satisfibility. For example, we add an edge between varibles and its negation to ensure that they are not in the same color. In other words, they couldn't be true at the same time.
c-allergic
commented
1 month ago
Coloring Problem
Given k kinds of colors and a Graph G=(V,E), color each vertice. Decide whether there is a way that no two adjcent vertices have the same color(Which means it's proper).
K-sat Problem
Reduce 3-sat to Coloring
Since these two problems are both condition constraints problems, it's useful to consider whether we could reduce one to another.
Here's how it works: