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_rvee i_gvee 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
