3NAE ≤p MAXCUT | Complexity Atlas

The construction

On a 3CNF formula $\varphi$ over $x_1,\dots,x_n$ with $m$ clauses:

Vertices. For each $1\le i\le n$ , a vertex for $x_i$ and one for $\overline{x_i}$ — $2n$ vertices, one per literal.
Blue edges (variable edges). For each $i$ , an edge between $x_i$ and $\overline{x_i}$ — $n$ edges.
Red edges (clause edges). For each clause, an edge between each pair of its literals — a triangle, $3$ edges per clause, $3m$ in all.
Return $\langle G,\ n+2m\rangle$ .

Why a multigraph. Two clauses sharing a literal pair produce parallel edges, and a clause containing both $x_i$ and $\overline{x_i}$ produces a red edge parallel to a blue one. These are distinct edges of the multigraph, and that is exactly what lets each clause be counted separately.

Visualization

Source NAE-3CNF(x ∨ y ∨ z) ∧ (¬x ∨ y ∨ ¬z)

Variable edgeClause edge

Correctness — both directions

3NAE ∈ ⟹ MAXCUT ∈

Suppose $\varphi\in\mathrm{3NAE}$ , with NAE-satisfying assignment $V$ . Define $U=\{\,\ell\ \mid\ \ell \text{ a literal vertex},\ V(\ell)=1\,\}.$

Blue edges. For each $i$ , exactly one of $x_i,\overline{x_i}$ gets $1$ (since $V(\overline{x_i})=1-V(x_i)$ ), so exactly one lies in $U$ ; the blue edge has $|e\cap U|=1$ and crosses. So all $n$ blue edges cross.

Red edges. Let $C$ be a clause with literals $\ell_1,\ell_2,\ell_3$ . Since $V$ NAE-satisfies $C$ , some $j$ has $\ell_j\in U$ and some $j'$ has $\ell_{j'}\notin U$ . The edge between $\ell_j$ and $\ell_{j'}$ crosses. That leaves the third vertex: whichever side it takes, exactly one of the two remaining edges crosses. So of the triangle's three edges exactly two cross.

Since red edges of distinct clauses are distinct multigraph edges, the counts add: $|\mathrm{cut}_G(U)|=\underbrace{n}_{\text{blue}}+\underbrace{2m}_{\text{red}}=n+2m\ \ge\ n+2m .$ Hence $\langle G,n+2m\rangle\in\mathrm{MAXCUT}$ .

MAXCUT ∈ ⟹ 3NAE ∈

Suppose $\langle G,n+2m\rangle\in\mathrm{MAXCUT}$ ; then some $U\subseteq V$ induces a cut with at least $n+2m$ edges.

Step 1 — an upper bound on the red edges. This needs the opposite kind of argument from everything so far: "at least" until now, "at most" here. Let $C$ be a clause with its triangle. Whatever $U$ is: either all three vertices sit on one side ( $0$ crossing) or they split $2$ – $1$ (exactly $2$ crossing). So each clause contributes at most $2$ red crossing edges, at most $2m$ overall.

Step 2 — forcing the blue edges. The cut has at least $n+2m$ edges, at most $2m$ of them red, so at least $n$ blue. But the graph has exactly $n$ blue edges in total. So the cut has exactly $n$ blue edges — all of them. Hence for every $i$ the edge $x_i\overline{x_i}$ crosses, i.e. exactly one of $x_i,\overline{x_i}$ lies in $U$ .

Step 3 — the assignment. Define $V(\ell)=1\iff\ell\in U$ for every literal vertex. By Step 2 this is consistent and well defined: from each pair $\{x_i,\overline{x_i}\}$ exactly one is in $U$ , so exactly one gets $1$ and the other $0$ .

Step 4 — every clause is NAE-satisfied. The cut holds exactly $n$ blue edges, so of the at least $n+2m$ edges, at least $2m$ are red. On the other hand each clause contributes at most $2$ ; if one contributed less than $2$ the total would fall below $2m$ — contradiction. So every clause contributes exactly two.

Let $C$ be a clause. Were all three of its vertices on one side it would contribute $0$ . So it splits: some $\ell\in C$ has $\ell\in U$ , i.e. $V(\ell)=1$ , and some $\ell'\in C$ has $\ell'\notin U$ , i.e. $V(\ell')=0$ . That is precisely NAE-satisfaction. As $C$ was arbitrary, $\varphi\in\mathrm{3NAE}$ .

Cost of the reduction

TimeO(|φ|)

SpaceO(|φ|)

Output sizeO(|φ|)

Linear, and that is the point: clause edges number exactly three per clause, because the formula is 3CNF. Red edges total $3m\le3|\varphi|$ . Had clauses been of arbitrary length, the edges per clique would be quadratic in clause length — and this would not be linear.

What it buys

$\mathrm{MAXCUT}$ is NP-hard, and lies in $\mathrm{NP}$ (witness $U$ ; the verifier counts edges with $|e\cap U|=1$ ), hence NP-complete. The simple-graph version stays hard — see $\mathrm{MAXCUT\text{-}MULTI}\le_p\mathrm{MAXCUT\text{-}SIMPLE}$ .

Pitfalls

Why exactly $3$ . The trick is that a triangle contributes exactly $2$ or exactly $0$ — nothing else is possible. For a clause of size $4$ or $5$ the free vertices can split several ways and the crossing count is no longer forced; the upper bound in Step 1 goes slack and the forcing in Step 2 breaks.
There is no "running the reduction backwards". In the $\Leftarrow$ direction students tend to think a formula must be built from a graph. It must not: we began with a given $\varphi$ , from which the algorithm built $G$ , so we hold both and know exactly what $G$ looks like. At no point do we say "let $G$ be a graph".

The chain

Rests on

4NAE ≤p 3NAE

Used later by

Max-Cut-Multi ≤p Max-Cut

Where this was read from

Lesson 10משפט 4: $\mathrm{3NAE} \le_p \mathrm{MAXCUT}$ , ולכן $\mathrm{MAXCUT}$ היא NP-קשה
Guided exercisemax-cut-multi-nae-reduction
2026"Prove the described algorithm is a polynomial-time reduction from 3-NAE to Max-Cut-Multi" — the paper spells the construction out in full.