Classical NP-Completeness Reductions: Examples and Counterexamples

In the graph defined in the example, choose the vertices labeled by the literal $z$ in the first, second, and third clauses. These occurrences come from different clauses and no two are complementary, so every pair is adjacent. Thus they form a clique of size $3$.

The assignment $z=1$ satisfies all three clauses of $\phi$, so the explicitly constructed clique agrees with the iff asserted by [L1]. This concrete yes-instance therefore illustrates the reduction theorem and, through [L2], the NP-completeness conclusion for CLIQUE.

Under the given assignment, both NAE clauses are satisfied: $(x,y,s)=(1,0,0)$ is not all equal, and $(\mathrm{\neg }s,z,w)=(1,0,0)$ is not all equal.

Define the graph directly: take a distinguished vertex $\nu$; for each variable $u\in \{x,y,z,w,s\}$ add the triangle $(u,\mathrm{\neg }u,\nu )$; for each of the two ordered NAE clauses add a triangle of three position vertices and join its $r$th vertex to the literal vertex in position $r$. Colour $\nu$ by $2$. In the variable triangles, colour each literal vertex by its Boolean value, so $x,\mathrm{\neg }x$ receive $1,0$, $y,\mathrm{\neg }y$ receive $0,1$, $z,\mathrm{\neg }z$ receive $0,1$, $w,\mathrm{\neg }w$ receive $0,1$, and $s,\mathrm{\neg }s$ receive $0,1$.

For the clause triangle for $N_1$, the literals $x$ and $y$ have different truth values, so colour their two position vertices by the opposite colours $0$ and $1$, and colour the remaining position vertex by $2$. Do the same for $N_2$. Every clause triangle then uses $0,1,2$, and each clause vertex differs from the colour of its adjacent literal vertex. Thus the explicitly defined graph is properly three-coloured.

This worked instance shows concretely how the theorem's NAE assignment is converted into a proper three-colouring.

The constant map in the given data is total and polynomial-time, and every satisfiable $3$-CNF formula is sent to the yes-instance $(K_1,1)$. So it preserves yes-instances in exactly the way promised by [L2].

Consider the unsatisfiable formula $(x\vee x\vee x)\wedge (\mathrm{\neg }x\vee \mathrm{\neg }x\vee \mathrm{\neg }x)$. It is still mapped to $(K_1,1)$, which is a yes-instance by [F1]. Thus the reverse implication in [L1] fails, so the map is not a correct many-one reduction.

This explicit map therefore refutes the slogan [L2].