[Solved]: 3 Colorability reduction to SAT

Problem Detail: 

I'd like to reduce 3 colorability to SAT. I've stuffed up somewhere because I've shown it's equivalent to 2 SAT.

Given some graph $G = (V,E)$ and three colors, red, blue, green. For every vertex $i$, let the boolean variable $i_r$ tell you whether the $i$-th vertex is red (or more precisely, that the $i$-th vertex is red when $i_r = 1$). Similarly, define $i_b$ and $i_g$.

Suppose two vertices $i$ and $j$ were connected by an edge $e$. Consider the clause \begin{align} (\bar i_r \vee \bar j_r) \end{align} If we demand the clause is true, it means that the vertices cannot both be red at the same time. Now consider the bigger clause $\phi_e$ \begin{align} (\bar i_r \vee \bar j_r)\wedge(\bar i_b \vee \bar j_b)\wedge(\bar i_g \vee \bar j_g) \end{align} which, if true, demands that the vertices $i$ and $j$ aren't both the same color. By itself, this clause is in 2-SAT.

For every edge $e \in E$, I now make a clause $\phi_e$ of the above form and put them all together using $\wedge$'s \begin{align} \phi = \wedge_{e \in E} \phi_e \end{align} Thus, for the entire graph, I've come up with a 2SAT formula which is equivalent to 3 coloring.

This is obviously wrong, but I can't tell where I've screwed up.

Asked By : WiFO215

Answered By : Emeu

With your modeling, setting $i$, $i_r$, $i_g$ and $i_b$ to false for all vertices yields a solution of the SAT problem and this is not a solution of the graph coloring problem.

You need to add clauses to say that each vertex is blue or green or red, namely $(i_r\vee i_g\vee i_b)$. Then it becomes a 3-SAT problem.

Note that if a vertex is assigned to more then one color, then we can take any of its colors and obtain a 3-coloring.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/13082

 Ask a Question

 Download Related Notes/Documents