Home / Computer science / 3-coloring (3COL)
Reduce
… 3SAT to 3COL, showing NP-completeness of the latter.
Perform a polynomial-time reduction using the graph below.
- Add three interconnected vertices, colored 1, 2, and 3.
- For each variable, add two uncolored vertices connected to 2.
- For each clause, add one Or gadget connected to:
- the relevant variable vertices and
- the vertex colored 1.
Given
\begin{equation*} F = c_1 \land c_2 \land \cdots = (\ell_{11} \lor \ell_{12} \lor \ell_{13}) \land (\ell_{21} \lor \ell_{22} \lor \ell_{23}) \land \cdots, \end{equation*}connect the graph
\begin{tikzpicture}[thick]
\usetikzlibrary{fit}
\usetikzlibrary{patterns}
% Styles
\tikzstyle{vertex} = [draw, circle, minimum size = 4ex]
%%%%%%%%%%%%%%%
%%% INPUT 1 %%%
%%%%%%%%%%%%%%%
% Nodes.
\node[vertex] (in 1 0) {};
\node[vertex, below of = in 1 0, node distance = 6ex] (in 1 1) {};
% Edge.
\draw (in 1 0) -- (in 1 1);
% Group
\node[draw, dotted, fit = (in 1 1) (in 1 0)] {};
% Notes
\node[right of = in 1 0, node distance = 8ex] (in 1 0 note) {$x_1$};
\node[right of = in 1 1, node distance = 8ex] (in 1 1 note) {$\lnot x_1$};
\draw (in 1 0) -- (in 1 0 note) [dashed];
\draw (in 1 1) -- (in 1 1 note) [dashed];
%%%%%%%%%%%%%%%
%%% INPUT 2 %%%
%%%%%%%%%%%%%%%
% Nodes
\node[vertex, below of = in 1 1, node distance = 9ex] (in 2 0) {};
\node[vertex, below of = in 2 0, node distance = 6ex] (in 2 1) {};
% Edge
\draw (in 2 0) -- (in 2 1);
% Group
\node[draw, dotted, fit = (in 2 1) (in 2 0)] {};
% Notes
\node[right of = in 2 0, node distance = 8ex] (in 2 0 note) {$x_2$};
\node[right of = in 2 1, node distance = 8ex] (in 2 1 note) {$\lnot x_2$};
\draw (in 2 0) -- (in 2 0 note) [dashed];
\draw (in 2 1) -- (in 2 1 note) [dashed];
%%%%%%%%%%%%%%%%
%%% INPUT 3+ %%%
%%%%%%%%%%%%%%%%
\node[below of = in 2 1, node distance = 6ex] (in dots) {\vdots};
%%%%%%%%%%%%%%
%%% OUTPUT %%%
%%%%%%%%%%%%%%
% Nodes
\node[
vertex,
below of = in dots,
node distance = 8ex,
pattern=north east lines
] (out 1) {1};
\node[
vertex,
left of = out 1,
node distance = 6ex,
pattern=north east lines
] (out 0) {0};
% Edge
\draw (out 0) -- (out 1);
% Group
\node[draw, dotted,
fit = (out 0) (out 1),
label = below: {$F = c_1 \land c_2 \land \cdots$}
] {};
%%%%%%%%%%%%%%%%%%%%%
%%% NON-1/0 COLOR %%%
%%%%%%%%%%%%%%%%%%%%%
% Node
\node[vertex, left of = in 2 0, node distance = 12ex, yshift = -3ex, pattern=north east lines] (2) {2};
% Edges
\draw
(2) -- (in 1 0) -- (2) -- (in 1 1)
(2) -- (in 2 0) -- (2) -- (in 2 1)
(2) -- (out 0) -- (2) -- (out 1);
%%%%%%%%%%%%%%%%%%%
%%% OR GADGET 1 %%%
%%%%%%%%%%%%%%%%%%%
% Nodes
\node[vertex, right of = in 1 0, node distance = 22ex] (or 1 1) {};
\node[vertex, below of = or 1 1, node distance = 6ex] (or 1 2) {};
\node[vertex, below of = or 1 2, node distance = 6ex] (or 1 3) {};
\node[vertex, right of = or 1 1, node distance = 6ex] (or 1 4) {};
\node[vertex, right of = or 1 3, node distance = 6ex] (or 1 5) {};
% Edges
\draw (or 1 4) -- (or 1 2) -- (or 1 1) -- (or 1 4) -- (or 1 5) -- (or 1 3);
% Group
\node[draw, dotted,
fit = (or 1 1) (or 1 2) (or 1 3) (or 1 4) (or 1 5),
label = {$c_1 = \ell_{11} \lor \ell_{12} \lor \ell_{13}$}
] {};
% Output
\draw (or 1 3) -- (out 1);
\draw (or 1 5) -- (out 1);
% Notes
\node[left of = or 1 1] (or 1 1 note) {$\ell_{11}$};
\node[left of = or 1 2] (or 1 2 note) {$\ell_{12}$};
\node[left of = or 1 3] (or 1 3 note) {$\ell_{13}$};
\draw (or 1 1) -- (or 1 1 note) [dashed];
\draw (or 1 2) -- (or 1 2 note) [dashed];
\draw (or 1 3) -- (or 1 3 note) [dashed];
%%%%%%%%%%%%%%%%%%%
%%% OR GADGET 2 %%%
%%%%%%%%%%%%%%%%%%%
% Nodes
\node[vertex, right of = or 1 1, node distance = 22ex] (or 2 1) {};
\node[vertex, below of = or 2 1, node distance = 6ex] (or 2 2) {};
\node[vertex, below of = or 2 2, node distance = 6ex] (or 2 3) {};
\node[vertex, right of = or 2 1, node distance = 6ex] (or 2 4) {};
\node[vertex, right of = or 2 3, node distance = 6ex] (or 2 5) {};
% Edges
\draw (or 2 4) -- (or 2 2) -- (or 2 1) -- (or 2 4) -- (or 2 5) -- (or 2 3);
% Group
\node[draw, dotted,
fit = (or 2 1) (or 2 2) (or 2 3) (or 2 4) (or 2 5),
label = {$c_2 = \ell_{21} \lor \ell_{22} \lor \ell_{23}$}
] {};
% Output
\draw (or 2 3) -- (out 1);
\draw (or 2 5) -- (out 1);
% Notes
\node[left of = or 2 1] (or 2 1 note) {$\ell_{21}$};
\node[left of = or 2 2] (or 2 2 note) {$\ell_{22}$};
\node[left of = or 2 3] (or 2 3 note) {$\ell_{23}$};
\draw (or 2 1) -- (or 2 1 note) [dashed];
\draw (or 2 2) -- (or 2 2 note) [dashed];
\draw (or 2 3) -- (or 2 3 note) [dashed];
%%%%%%%%%%%%%%%%%%%%
%%% OR GADGET 3+ %%%
%%%%%%%%%%%%%%%%%%%%
\node[right of = or 2 2, node distance = 14ex] {$\cdots$};
\end{tikzpicture}
For example,
\begin{equation*} F = (\lnot x_1 \lor x_2 \lor \lnot x_2) \land (\lnot x_2 \lor x_3 \lor \lnot x_3) \end{equation*}reduces to the graph
\begin{tikzpicture}[thick]
\usetikzlibrary{fit}
\usetikzlibrary{patterns, positioning}
% Styles
\tikzstyle{vertex} = [draw, circle, minimum size = 4ex]
% Inputs
\node[vertex] (in x_1) {};
\node[vertex, below of = in x_1, node distance = 6ex] (in not x_1) {};
\draw (in not x_1) -- (in x_1);
\node[draw, dotted, fit = (in x_1) (in not x_1), label = {$x_1, \lnot x_1$}];
\node[vertex, below of = in not x_1, node distance = 10ex] (in x_2) {};
\node[vertex, below of = in x_2, node distance = 6ex] (in not x_2) {};
\draw (in not x_2) -- (in x_2);
\node[draw, dotted, fit = (in x_2) (in not x_2), label = {$x_2, \lnot x_2$}];
\node[vertex, below of = in not x_2, node distance = 10ex] (in x_3) {};
\node[vertex, below of = in x_3, node distance = 6ex] (in not x_3) {};
\draw (in not x_3) -- (in x_3);
\node[draw, dotted, fit = (in x_3) (in not x_3), label = {$x_3, \lnot x_3$}];
% Output
\node[
vertex,
below of = in not x_3,
node distance = 10ex,
pattern = north east lines
] (out 1) {1};
\node[
vertex,
left of = out 1,
node distance = 6ex,
pattern = north east lines
] (out 0) {0};
\draw (out 0) -- (out 1);
\node[
draw,
dotted,
fit = (out 0) (out 1),
label = below: {$F = c_1 \land c_2$}
];
% The "2" node.
\node[
vertex,
left of = in not x_2,
node distance = 16ex,
yshift = 3ex,
pattern=north east lines
] (2) {2};
\draw
(2) -- (in not x_1) -- (2) -- (in x_1)
(2) -- (in not x_2) -- (2) -- (in x_2)
(2) -- (in not x_3) -- (2) -- (in x_3)
(2) -- (out 0) -- (2) -- (out 1);
% Or 1
\node[vertex, right of = in x_1, node distance = 12ex] (or 1 1);
\node[vertex, below of = or 1 1, node distance = 6ex] (or 1 2);
\node[vertex, below of = or 1 2, node distance = 6ex] (or 1 3);
\draw (in not x_1) -- (in x_1);
\draw (in not x_2) -- (in x_2);
\draw (in not x_3) -- (in x_3);
\node[vertex, right of = or 1 1, node distance = 6ex] (or 1 4);
\node[vertex, right of = or 1 3, node distance = 6ex] (or 1 5);
\draw (or 1 1) -- (or 1 2);
\draw (or 1 1) -- (or 1 4) -- (or 1 2);
\draw (or 1 4) -- (or 1 5);
\draw (or 1 5) -- (or 1 3);
\node[
draw,
dotted,
fit = (or 1 1) (or 1 2) (or 1 3) (or 1 4) (or 1 5),
label = {$c_1 = \lnot x_1 \lor x_2 \lor \lnot x_2$}
];
% Or 2
\node[vertex, right of = in not x_2, node distance = 24ex] (or 2 1);
\node[vertex, below of = or 2 1, node distance = 6ex] (or 2 2);
\node[vertex, below of = or 2 2, node distance = 6ex] (or 2 3);
\draw (in not x_1) -- (in x_1);
\draw (in not x_2) -- (in x_2);
\draw (in not x_3) -- (in x_3);
\node[vertex, right of = or 2 1, node distance = 6ex] (or 2 4);
\node[vertex, right of = or 2 3, node distance = 6ex] (or 2 5);
\draw (or 2 1) -- (or 2 2);
\draw (or 2 1) -- (or 2 4) -- (or 2 2);
\draw (or 2 4) -- (or 2 5);
\draw (or 2 5) -- (or 2 3);
\node[
draw,
dotted,
fit = (or 2 1) (or 2 2) (or 2 3) (or 2 4) (or 2 5),
label = {$c_2 = \lnot x_2 \lor x_3 \lor \lnot x_3$}
];
% Connect outputs
\draw (or 1 3) -- (out 1);
\draw (or 1 5) -- (out 1);
\draw (or 2 3) -- (out 1);
\draw (or 2 5) -- (out 1);
% Connect inputs
\draw (in not x_1) -- (or 1 1);
\draw (in x_2) -- (or 1 2);
\draw (in not x_2) -- (or 1 3);
\draw (in not x_2) -- (or 2 1);
\draw (in x_3) -- (or 2 2);
\draw (in not x_3) -- (or 2 3);
\end{tikzpicture}
