Reduce NAE-3SAT to multigraph Max-Cut

Build variable and clause multiedges so a cut of size n+2m encodes a not-all-equal assignment.

Problem

Let NAE-3SAT be the language of 3CNF formulas that admit a truth assignment under which every clause has at least one true literal and at least one false literal. Let Max-Cut-Multi receive a multigraph $G$ and integer $K$ and ask whether some cut has at least $K$ crossing edges (counting multiplicity).

Given a 3CNF formula $\varphi$ on $n$ variables and $m$ clauses (each clause uses three distinct variables), construct a multigraph $G$ and threshold $K=n+2m$ such that $\varphi\in\mathrm{NAE\text{-}3SAT}$ if and only if $(G,K)$ is a yes instance of Max-Cut-Multi. Prove both directions and polynomial size.

Hint 1

Vertices should represent literals $x_i$ and $\neg x_i$.

Hint 2

Reward cutting each variable pair once, and cutting two of the three edges inside each clause triple.

Full solution

Create vertices $\{x_1,\neg x_1,\ldots,x_n,\neg x_n\}$. Add one edge $\{x_i,\neg x_i\}$ for each variable (the variable edges). For each clause $(\ell_a\lor\ell_b\lor\ell_c)$ add the three clause edges $\{\ell_a,\ell_b\}$, $\{\ell_b,\ell_c\}$, $\{\ell_c,\ell_a\}$, allowing parallel edges when the same literal pair recurs. Output $K=n+2m$.

Any cut corresponds to a partition of literals. A consistent assignment places exactly one of $x_i,\neg x_i$ on each side: then all $n$ variable edges are cut. If some pair lies on the same side, that variable edge contributes $0$. Inside a clause triangle, the number of cut edges is $2$ when the three literals are not monochromatic under the side-coloring, and at most $0$ or (with parallel structure) otherwise at most $2$ only in the NAE pattern; with simple triangles, a $3$-way split is impossible on two sides, so the cut contributes $2$ exactly on NAE patterns and $0$ when all three literals lie on one side. Summing yields at most $n+2m$, with equality if and only if every variable pair is split and every clause is not-all-equal.

Conversely, from a cut of size $n+2m$ recover the side of each positive literal as truth, after noting that each complementary pair must be separated (else the total cannot reach $K$). Polynomial size is immediate: $2n$ vertices and $n+3m$ edge endpoints to list.

Checkpoint

Consistency of complements is enforced by variable edges; NAE (not merely SAT) is enforced by scoring $2$ per clause rather than $1$.

Common mistakes

• Using threshold $n+3m$ or $n+m$, which breaks the tight NAE characterization.
• Forgetting multiedges when a literal pair appears in several clauses.
• Allowing both $x$ and $\neg x$ on the same side while still claiming size $K$.

Provenance note

Independently written exposition of the reduction family appearing in Semester A 2026 exercise 4 (Q2). The narrative and proof text are original; the assignment is cited as provenance for the construction parameters, not as copied solution text.

Sources and verification

• Semester A 2026 exercise 4, Q2
• Course Max-Cut lecture notes
• Catalog mapping: data/exercises.json; statements and solutions are independently written.

Open in the visualization gallery: NAE-3SAT → Max-Cut