3NAE ≤p 3COL | Complexity Atlas

The construction

On a 3CNF formula $\varphi$ over $x_1,\dots,x_n$ with $m$ clauses. The output is a graph alone — no number, since $k=3$ is part of the problem's DNA.

Vertices. For each $i$ , a vertex for $x_i$ and one for $\overline{x_i}$ (literal vertices); one special vertex $N$ ; and for each clause $C_j$ three further vertices, one per literal (clause vertices). In all $2n+1+3m$ vertices.
Edges.
- Black: $N$ to every literal vertex — $2n$ edges.
- Blue: every literal to its negation — $n$ edges.
- Red: per clause, a triangle on its three clause vertices, plus an edge from each clause vertex to its corresponding literal vertex — $3+3=6$ edges per clause.
Return $G$ .

The intuition. In a legal colouring, w.l.o.g. $f(N)=1$ . Since $N$ is joined to every literal vertex, each literal vertex is coloured $2$ or $3$ ; and since $x_i$ is joined to $\overline{x_i}$ , exactly one of each such pair is $2$ and exactly one is $3$ . The colours $\{2,3\}$ behave exactly like $\{\text{true},\text{false}\}$ , with $N$ "burning" the first colour for us. The triangles enforce the NAE condition.

A distinction that confused the class: each clause has three vertices of its own, objects separate from the literal vertices. A clause vertex "corresponds" to a literal only in the sense that a red edge joins them.

Visualization

Input φ(x ∨ y ∨ z) ∧ (¬x ∨ y ∨ ¬z)

Correctness — both directions

3NAE ∈ ⟹ 3COL ∈

Suppose $\varphi\in\mathrm{3NAE}$ , with NAE-satisfying assignment $V$ . Build a colouring $f$ :

$f(N)=1$ .
For each $i$ : if $V(x_i)=1$ then $f(x_i)=2$ , $f(\overline{x_i})=3$ ; otherwise $f(x_i)=3$ , $f(\overline{x_i})=2$ . Equivalently, the uniform rule $f(\ell)=2\iff V(\ell)=1,\qquad f(\ell)=3\iff V(\ell)=0\qquad(\ast)$
Let $C$ be a clause with literals $\ell_1,\ell_2,\ell_3$ and clause vertices $c_1,c_2,c_3$ ( $c_t$ joined to $\ell_t$ ). Since $V$ NAE-satisfies $C$ , some $t$ has $V(\ell_t)=1$ and some $t'$ has $V(\ell_{t'})=0$ ; pick one of each and colour $f(c_t)=3$ , $f(c_{t'})=2$ , $f(c_{t''})=1$ for the third.

Now check no edge is monochromatic:

Black: $f(N)=1$ while every literal has $f(\ell)\in\{2,3\}$ . ✓
Blue: by step 2 one is $2$ and the other $3$ . ✓
Clause triangle: the three vertices got $3,2,1$ — three distinct colours. ✓
Red, clause vertex to its literal: $f(c_t)=3$ while by $(\ast)$ $f(\ell_t)=2$ ; $f(c_{t'})=2$ while by $(\ast)$ $f(\ell_{t'})=3$ ; and $f(c_{t''})=1$ while $f(\ell_{t''})\in\{2,3\}$ . ✓ (Colour $1$ is always free for a clause vertex, since only $N$ takes it and $N$ is not joined to clause vertices.)

So $f$ is a legal 3-colouring, i.e. $G\in\mathrm{3COL}$ .

3COL ∈ ⟹ 3NAE ∈

Let $f$ be a legal 3-colouring of $G$ . Since permuting colour names preserves legality, w.l.o.g. $f(N)=1$ .

Step 1. Every literal vertex $\ell$ is joined to $N$ by a black edge, so $f(\ell)\ne1$ , i.e. $f(\ell)\in\{2,3\}$ .

Step 2. For each $i$ the blue edge $x_i\overline{x_i}$ forces $f(x_i)\ne f(\overline{x_i})$ . With Step 1: exactly one of $x_i,\overline{x_i}$ is coloured $2$ and the other $3$ .

Step 3 (the assignment). Define $V(x_i)=1\iff f(x_i)=2$ . By Step 2 this makes $f(\overline{x_i})=3$ , so the uniform rule $(\ast)$ holds again. The definition is consistent and well defined for every variable.

Step 4 (every clause is NAE-satisfied). Let $C$ be a clause with literals $\ell_1,\ell_2,\ell_3$ and clause vertices $c_1,c_2,c_3$ . The three form a triangle, so in a legal colouring they carry three distinct colours: $\{f(c_1),f(c_2),f(c_3)\}=\{1,2,3\}$ . In particular:

some $t$ has $f(c_t)=2$ . The red edge $c_t\ell_t$ forces $f(\ell_t)\ne2$ , and Step 1 gives $f(\ell_t)=3$ , so by $(\ast)$ $V(\ell_t)=0$ .
some $s$ has $f(c_s)=3$ . The red edge $c_s\ell_s$ forces $f(\ell_s)\ne3$ , so $f(\ell_s)=2$ , so $V(\ell_s)=1$ .

And $t\ne s$ since the colours differ, so $\ell_t\ne\ell_s$ are two distinct literals of $C$ — this is where the assumption of three distinct literals per clause enters.

So $C$ holds a literal assigned $1$ and one assigned $0$ , i.e. $V$ NAE-satisfies $C$ . As $C$ was arbitrary, $\varphi\in\mathrm{3NAE}$ .

Cost of the reduction

TimeO(|φ|)

SpaceO(|φ|)

Output sizeO(|φ|)

What it buys

$\mathrm{3COL}$ is NP-hard, and lies in $\mathrm{NP}$ (witness the colouring; the verifier scans the edges), hence NP-complete. From there $\mathrm{4COL}$ follows through $\mathrm{3COL}\le_p\mathrm{4COL}$ .

Pitfalls

You cannot colour "all $x_i$ with 2 and all $\overline{x_i}$ with 3". The colouring must depend on the assignment; otherwise two literals the assignment valued differently would share a colour and the link between colour and truth value would break.
Each clause triangle is coloured completely independently of the others — just as in the $\mathrm{MAXCUT}$ reduction each clause contributed its own edges.

The chain

Rests on

4NAE ≤p 3NAE

Used later by

3COL ≤p 4COL

Where this was read from

Lesson 10משפט 6: $\mathrm{3NAE} \le_p \mathrm{3COL}$ , ולכן $\mathrm{3COL}$ היא NP-שלמה

The $\Longleftarrow$ direction was left as homework in the lecture and only sketched in the recording's final minute; the full proof in the lesson file is a completion following the lecturer's sketch.