2
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ How do you make sure that every node gets a color? $\endgroup$
    – adrianN
    Commented Jul 4, 2013 at 11:40
  • $\begingroup$ As @adrianN says, consider the assignment $\alpha(i_r) = \alpha(i_g) = \alpha(i_b) = \bot$ for all $i \in V$. $\endgroup$
    – John Kemeny
    Commented Jul 4, 2013 at 12:07

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks @adrianN and A.Schulz. I see what I'm missing. Here's what I still do not understand. The statement $\phi$ that I've got above is 2SAT. I will have to add the clauses $(i_r \vee i_g \vee i_b)$ to $\phi$ for every vertex $i$, each of which is 3SAT. However, the statement $\phi$ itself is only 2SAT and by adding the above statements, I'll have a mixture of 2SAT and 3SAT statements. I know how to 'dilate' all 2SAT clauses in $\phi$ to 3SAT by adding dummy variables. That is what I have to do to make the entire coloring problem 3SAT, correct? $\endgroup$
    – WiFO215
    Commented Jul 4, 2013 at 16:22
  • $\begingroup$ Actually, you don't need any dummy variable: any 2-clause $(\overline{i_b}\vee\overline{i_g})$ can be extended to an equivalent 3-clause $(\overline{i_b}\vee\overline{i_g}\vee\overline{i_g})$ by duplicating one litteral. $\endgroup$
    – Emeu
    Commented Jul 6, 2013 at 8:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.