Rudolf Adamkovič Personal site


3COL

a.k.a.

Define

… as a special case of COL with

exactly three colors.

Reduce

3SAT to 3COL, showing NP-completeness of the latter.

Perform a polynomial-time reduction using the graph below.

  1. Create the first vertex colored 2.
  2. Add 0/1 inputs for each variable.
  3. Add 0/1 output.
  4. For each clause:
    1. Add a new Or gadget.
    2. Connect the gadget to the appropriate inputs.
    3. Connect the gadget the 1 output.
\[\begin{equation*}
  F = c_1 \land c_2 \land \cdots = (\ell_{11} \lor \ell_{12} \lor \ell_{13}) \land \cdots
\end{equation*}
\]

The gadgets:

babel-results/0e31ff94-c745-49ab-a42b-985b2a1ac01b

For example,

\[\begin{equation*}
  (x_1 \lor \lnot x_2 \lor x_2) \land (x_2 \lor \lnot x_3 \lor x_3)
\end{equation*}
\]

is reduced to:

babel-results/a2215ee0-36af-4e1f-8d8f-c8ff4fda71c4

Check

… that Or gadget implements the 3-way disjunction

\[\begin{equation*}
  \ell_1 \lor \ell_2 \lor \ell_3.
\end{equation*}
\]

The Or gadget:

babel-results/0ceb40bf-4e47-4aee-89db-b404445c4ee9

No coloring exists when \(\ell_1 = \ell_2 = \ell_3 = 0\):

\(\ell_1\)\(\ell_2\)\(\ell_3\)\(c_1\)\(c_2\)\(c_3\)\(c_4\)\(c_5\)
000n/a1220
000n/a2210
0001n/a220
0002n/a210
00012n/a02
00021n/a02
000122n/a0
000212n/a0
0001220n/a
0002120n/a

Otherwise, a coloring exists:

\(\ell_1\)\(\ell_2\)\(\ell_3\)\(c_1\)\(c_2\)\(c_3\)\(c_4\)\(c_5\)
00112002
00121002
01010220
01020210
01120012
01120210
10001220
10002210
10102012
10102210
11002210
11020210
11102012
11102210
11120012
11120210


© 2024 Rudolf Adamkovič under GNU General Public License version 3.
Made with Emacs and secret alien technologies of yesteryear.