3-color to SAT reduction

3-color-to-SAT-reduction.md

$\textsf{3-color} \leqslant \textsf{SAT}$

Written with StackEdit and the math expression can be rendered in its viewer.

We have proved that $\textsf{3-color}$ is $\textbf{NP}$-complete by reducing $\textsf{SAT}$ to $\textsf{3-color}$. Is there a polynomial-time reduction form $\textsf{3-color}$ to $\textsf{SAT}$? If there is, give one such reduction.

Final exam of CSIE3110: Formal language and automata theory, 10th January, 2017.

To reduce $\textsf{3-color}$ to $\textsf{SAT}$, we transform the problem instance of $\textsf{3-color}$ $G = \langle V, E \rangle$ to the problem instance of $\textsf{SAT}$ $\phi$ in polynomial time.

To construct the CNF $\phi$, we use

1. Two literals $x_i$ and $y_i$ to represent the color of each vertex in $V$, and
2. A clause $\phi_{i, j}$ to represent the coloring constraint for each edge $(i, j)$ in $E$.

Because there are only three colors available for coloring, we choose the pair $(x_i, y_i) \in { (\top, \top), (\top, \bot), (\bot, \top) }$ to be one of the three color. To eliminate the fourth choice $(\bot, \bot)$, we assert that $(x_i \vee y_i)$ must be $\top$ for each $i \in { 1, 2, \cdots, |V| }$.

Furthermore, for each pair of vertices of any edge, their color must be different. That is, $(x_i, y_i) \neq (x_j, y_j)$ for all edges $(i, j)$. We express $p \neq q$ by the clause $(p \vee q) \wedge (\overline{p} \vee \overline{q})$. The remaining work is to show $\phi_{i, j}$ in CNF as follows,

$$\begin{align} \phi_{i, j} &= (x_i \neq x_j) \vee (y_i \neq y_j) \\ &= \Big[ (x_i \vee x_j) \wedge (\overline{x_i} \vee \overline{x_j}) \Big] \vee \Big[ (y_i \vee y_j) \wedge (\overline{y_i} \vee \overline{y_j}) \Big] \\ &= (x_i \vee x_j \vee y_i \vee y_j) \wedge (x_i \vee x_j \vee \overline{y_i} \vee \overline{y_j}) \ \wedge \\ &\phantom{=\ } (\overline{x_i} \vee \overline{x_j} \vee y_i \vee y_j) \wedge (\overline{x_i} \vee \overline{x_j} \vee \overline{y_i} \vee \overline{y_j}). \end{align}$$

In the last equality, we used the fact that OR is distributive to AND. That is, $(p \wedge q) \vee r \equiv (p \vee r) \wedge (q \vee r)$. So $\phi_{i, j}$ can be expressed as 4-CNF.

To meet all the constraints, we therefore claim that the 4-CNF $$ \phi = \Bigg[\bigwedge_{i=1}^{|V|} (x_i \vee y_i) \Bigg] \wedge \Bigg[ \bigwedge_{(i, j) \in E} \phi_{i, j} \Bigg] $$ is satisfiable iff. the graph $G$ is 3-colorable. This completes the reduction.

Complexity analysis: The transformation produce a 4-CNF with $|V| + 4|E|$ clauses, and the number of literals used to compose $\phi$ is $2|V|$, which are all computable in polynomial time.

Credits

Thanks Hsu, Heng-Yu for clarifying that the constraint of each edge can be expressed as a 4-CNF. I mistakenly expressed it as a 2-CNF when taking the exam and showed that the problem can be transformed to a $\textsf{2-SAT}$ (in $\textbf{P}$) instance, thinking that I've proved that $\textbf{P}=\textbf{NP}$.