Classical NP-Completeness Reductions

Construct a graph $G_{\phi }$ with one vertex $v_{jr}$ for each literal occurrence ${\mathrm{\ell }}_{jr}$ in clause $C_j$. Join $v_{jr}$ and $v_{j^{\mathrm{\prime }}{r}^{\mathrm{\prime }}}$ by an edge exactly when $j\mathrm{\ne }{j}^{\mathrm{\prime }}$ and the literals ${\mathrm{\ell }}_{jr}$ and ${\mathrm{\ell }}_{j^{\mathrm{\prime }}{r}^{\mathrm{\prime }}}$ are not complementary. Output the CLIQUE instance $(G_{\phi },m)$.

Assume that $\phi$ is satisfiable, and choose a satisfying assignment. For each clause $C_j$, pick one literal made true by that assignment and take the corresponding vertex of $G_{\phi }$. This gives $m$ chosen vertices, one from each clause. Two chosen literals cannot be complementary because one assignment cannot make a variable and its negation both true, so step 1.1 makes every chosen pair adjacent. Therefore the chosen vertices form an $m$-clique.

Assume conversely that $G_{\phi }$ has a clique $K$ of size $m$. By step 1.1, no two vertices from the same clause are adjacent, so $K$ contains exactly one vertex from each clause. Again by step 1.1, the literals represented by those vertices are pairwise noncomplementary. Assign truth values so that every chosen literal is true, and extend arbitrarily to variables not yet assigned. Then each clause contains its chosen true literal, so $\phi$ is satisfiable.

The graph $G_{\phi }$ has $3m$ vertices and at most $9m^2$ candidate edges, so the map in step 1.1 is computable in polynomial time. Steps 2.1 and 2.2 prove $\phi \in 3\text{-}SAT⟺(G_{\phi },m)\in CLIQUE\mathrm{.}$ By [L1] and [L2], this is a polynomial-time many-one reduction.

A certificate for $(G,k)\in CLIQUE$ is a list of $k$ vertices. One checks in polynomial time that the listed vertices are distinct and that every pair is adjacent, so CLIQUE lies in $NP$.

Because [L2] says that $3$-SAT is NP-complete, every language in $NP$ reduces to $3$-SAT. Composing any such reduction with the fixed reduction [L1] shows that every language in $NP$ reduces to CLIQUE. Hence CLIQUE is NP-hard.

Step 1.1 gives CLIQUE $\in NP$, and step 1.2 gives NP-hardness. Therefore CLIQUE is NP-complete by [L3].

For any subset $S\subseteq V$, [L1] implies that the vertices of $S$ are pairwise adjacent in $G$ if and only if they are pairwise nonadjacent in $\bar{G}$. Thus $S$ is a clique in $G$ if and only if it is an independent set in $\bar{G}$. Therefore $(G,k)\mapsto (\bar{G},k)$ is a polynomial-time many-one reduction from CLIQUE to INDEPENDENT SET, and the same map is also a reduction in the reverse direction.

For any subset $I\subseteq V$, the complement $V\setminus I$ is a vertex cover if and only if $I$ is an independent set. Indeed, if $I$ is independent, every edge has at least one endpoint outside $I$, so it is covered by $V\setminus I$. Conversely, if $V\setminus I$ is a vertex cover and two vertices of $I$ were adjacent, that edge would have no endpoint in $V\setminus I$, a contradiction. Hence, whenever $k\le \mathrm{\mid }V\mathrm{\mid }$, the graph $G$ has an independent set of size at least $k$ if and only if it has a vertex cover of size at most $\mathrm{\mid }V\mathrm{\mid }-k$.

Use step 1.2 to define total reductions. For INDEPENDENT SET to VERTEX COVER, map $(G,k)$ to $(G,\mathrm{\mid }V\mathrm{\mid }-k)$ when $k\le \mathrm{\mid }V\mathrm{\mid }$, and map it to the fixed no-instance $(K_2,0)$ when $k>\mathrm{\mid }V\mathrm{\mid }$. For VERTEX COVER to INDEPENDENT SET, map $(G,k)$ to $(G,\mathrm{\mid }V\mathrm{\mid }-k)$ when $k\le \mathrm{\mid }V\mathrm{\mid }$, and map it to the fixed yes-instance $(K_1,1)$ when $k>\mathrm{\mid }V\mathrm{\mid }$. The exceptional branches are correct because no graph has an independent set larger than its vertex set, while every graph has a vertex cover of size at most $\mathrm{\mid }V\mathrm{\mid }$. Both maps are clearly polynomial-time.

Step 1.1 gives reductions between CLIQUE and INDEPENDENT SET, and step 2.1 gives reductions between INDEPENDENT SET and VERTEX COVER. Composing these reductions yields reductions in every direction among the three problems.

A certificate for INDEPENDENT SET is a list of $k$ vertices, and one checks in polynomial time that no pair among them is adjacent. A certificate for VERTEX COVER is a list of at most $k$ vertices, and one checks in polynomial time that every edge has an endpoint in that list. Hence both problems lie in $NP$.

Since [L1] makes CLIQUE NP-complete, every language in $NP$ reduces to CLIQUE. Applying the reductions from [L2] from CLIQUE to INDEPENDENT SET and from CLIQUE to VERTEX COVER shows that every language in $NP$ reduces to each of those target problems. Therefore both targets are NP-hard.

Combine step 1.1 with step 1.2 and [L3]. Both INDEPENDENT SET and VERTEX COVER are NP-complete.

If $m=0$, then $\phi$ is the empty conjunction and is satisfiable. Let $D_{\phi }$ be the one-vertex digraph and name its unique vertex both $s_{\phi }$ and $t_{\phi }$; it has the required one-vertex Hamiltonian path. Adjoining $z_{\phi }$ and the two opposite arcs between $z_{\phi }$ and $s_{\phi }=t_{\phi }$ gives a directed Hamiltonian cycle. This is the required constant-size output in the empty case. Assume henceforth that $m\ge 1$, so at least one variable occurs. Enumerate the variables of $\phi$ as $x_1,\dots ,x_n$ and the clauses as $C_1,\dots ,C_m$. For each variable $x_i$, create vertices $p_i,q_i,s_{i,0},\dots ,s_{i,m},{\mathrm{\ell }}_{i,1},r_{i,1},\dots ,{\mathrm{\ell }}_{i,m},r_{i,m}\mathrm{.}$ The crossbar of the gadget $X_i$ is the bidirected path $s_{i,0}\leftrightarrow {\mathrm{\ell }}_{i,1}\leftrightarrow r_{i,1}\leftrightarrow s_{i,1}\leftrightarrow \cdots \leftrightarrow s_{i,m-1}\leftrightarrow {\mathrm{\ell }}_{i,m}\leftrightarrow r_{i,m}\leftrightarrow s_{i,m},$ and we also add the four boundary arcs $p_i\to s_{i,0},p_i\to s_{i,m},s_{i,0}\to q_i,s_{i,m}\to q_i\mathrm{.}$ Thus every Hamiltonian path from $p_i$ to $q_i$ inside $X_i$ must enter the crossbar at one end, traverse every crossbar vertex exactly once, and exit from the opposite end; equivalently it is either the left-to-right route through all clause pairs or the right-to-left route through all clause pairs. Identify $q_i$ with $p_{i+1}$ for $1\le i<n$, and write $s_{\phi }:=p_1$, $t_{\phi }:=q_n$. For each clause $C_j$, add one clause vertex $c_j$. If the literal $x_i$ occurs in $C_j$, add the two arcs ${\mathrm{\ell }}_{i,j}\to c_j,c_j\to r_{i,j};$ if the literal $\mathrm{\neg }{x}_i$ occurs in $C_j$, add $r_{i,j}\to c_j,c_j\to {\mathrm{\ell }}_{i,j}\mathrm{.}$ If both literals occur, add both pairs of arcs. This completely specifies the digraph $D_{\phi }$, which has $O(nm)$ vertices and arcs and is computable in polynomial time.

Suppose that $\phi$ is satisfiable. In each gadget $X_i$, choose the left-to-right crossbar route if $x_i=true$ and the right-to-left route if $x_i=false$. Concatenating these routes through the identified vertices $q_i=p_{i+1}$ already yields a directed path from $s_{\phi }$ to $t_{\phi }$ visiting every gadget vertex exactly once. Now fix a clause $C_j$, and choose one literal of $C_j$ that is true under the satisfying assignment. If it is a positive occurrence of $x_i$, replace the local edge ${\mathrm{\ell }}_{i,j}\to r_{i,j}$ on the left-to-right route by the detour ${\mathrm{\ell }}_{i,j}\to c_j\to r_{i,j}$. If it is a negative occurrence of $x_i$, replace the local edge $r_{i,j}\to {\mathrm{\ell }}_{i,j}$ on the right-to-left route by $r_{i,j}\to c_j\to {\mathrm{\ell }}_{i,j}$. Doing this once for each clause visits every clause vertex exactly once and does not revisit any gadget vertex, because each detour leaves and re-enters the same clause pair. Hence $D_{\phi }$ has a directed Hamiltonian path from $s_{\phi }$ to $t_{\phi }$.

Suppose conversely that $D_{\phi }$ has a directed Hamiltonian path from $s_{\phi }$ to $t_{\phi }$. We first verify the interface invariant omitted by a merely pictorial gadget argument. If the path enters a clause vertex $c_j$ from an occurrence pair in $X_i$ and leaves toward a different occurrence pair, then the unused vertex of the first pair can subsequently be entered only from its other crossbar neighbour; after that entry, every possible exit goes to that already visited neighbour, the visited mate, or the already visited clause vertex. The path is therefore stuck before reaching $t_{\phi }$. The same four-case check applies with the crossbar direction reversed and with positive and negative occurrence arcs exchanged. Hence every visit to $c_j$ leaves through the mate in the same occurrence pair: a clause visit only replaces one crossbar edge by its two-edge detour. It follows that the path cannot jump between variable gadgets through a clause vertex. The remaining connections force it through $X_1,\dots ,X_n$ in order, and within each $X_i$ it traverses the entire crossbar monotonically from one end to the other. Set $x_i=true$ exactly for a left-to-right traversal. Every clause vertex is visited by a same-pair detour whose orientation exists only for a literal made true by this assignment. Thus every clause has a true literal and $\phi$ is satisfiable.

Now add one fresh vertex $z_{\phi }$ and the two arcs $z_{\phi }\to s_{\phi }$ and $t_{\phi }\to z_{\phi }$. If $D_{\phi }$ has a Hamiltonian path from $s_{\phi }$ to $t_{\phi }$, then adjoining $z_{\phi }$ closes that path to a directed Hamiltonian cycle in $D_{\phi }^{\mathrm{\prime }}$. Conversely, any directed Hamiltonian cycle in $D_{\phi }^{\mathrm{\prime }}$ must pass through the fresh vertex $z_{\phi }$, whose only outgoing arc is to $s_{\phi }$ and whose only incoming arc is from $t_{\phi }$. Deleting $z_{\phi }$ from the cycle therefore yields a directed Hamiltonian path from $s_{\phi }$ to $t_{\phi }$ in $D_{\phi }$.

Step 1.1 handles the empty formula and gives a polynomial-time construction for every well-formed $3$-CNF formula. For $m\ge 1$, steps 2.1 and 2.2 prove the iff for directed Hamiltonian path, and step 3.1 converts that iff to directed Hamiltonian cycle. Extend the map to every input string by checking $3$-CNF syntax in polynomial time and sending any malformed string to the fixed one-vertex loopless digraph, which has no directed Hamiltonian cycle. By [L1] and [L2], the resulting total function is a polynomial-time many-one reduction from $3$-SAT to directed Hamiltonian cycle.

If $\mathrm{\mid }V\mathrm{\mid }\le 1$, decide directly whether $D$ has a directed Hamiltonian cycle and map it to a fixed yes-instance or no-instance of undirected Hamiltonian cycle accordingly. Thus it is enough to treat the case $\mathrm{\mid }V\mathrm{\mid }\ge 2$. Delete every loop, since a Hamiltonian cycle through at least two distinct vertices cannot use a loop. For each vertex $v\in V$, create three undirected vertices $v_1,v_2,v_3$ and the two edges $v_1{v}_2$ and $v_2{v}_3$. For each arc $(u,v)\in A$ with $u\mathrm{\ne }v$, add the undirected edge $u_3{v}_1$. Call the resulting graph $G_D$.

In any Hamiltonian cycle of $G_D$, the middle vertex $v_2$ has degree two, so the cycle must traverse the gadget for $v$ as the consecutive path $v_1,v_2,v_3$ or as the consecutive path $v_3,v_2,v_1$. Moreover, every external gadget edge joins a $3$-vertex to a $1$-vertex. Hence, after orienting the cycle, once one gadget is traversed in one of those two directions, every subsequent gadget is forced to be traversed in the same direction around the cycle.

If $D$ has a directed Hamiltonian cycle $v^{(1)}\to v^{(2)}\to \cdots \to v^{(n)}\to v^{(1)}$, then $v_1^{(1)},v_2^{(1)},v_3^{(1)},v_1^{(2)},v_2^{(2)},v_3^{(2)},\dots ,v_1^{(n)},v_2^{(n)},v_3^{(n)},v_1^{(1)}$ is a Hamiltonian cycle in $G_D$, because each directed arc $v^{(i)}\to v^{(i+1)}$ supplies the edge $v_3^{(i)}{v}_1^{(i+1)}$.

Conversely, let $C$ be a Hamiltonian cycle in $G_D$. By step 2.1 and, if necessary, reversing the orientation of $C$, we may assume that every gadget is traversed as $v_1,v_2,v_3$. Whenever $C$ moves from the gadget of $u$ to the gadget of $v$, it uses an edge $u_3{v}_1$, and such an edge exists only when $(u,v)\in A$. Replacing each gadget path $v_1,v_2,v_3$ by the single vertex $v$ therefore projects $C$ to a directed Hamiltonian cycle of $D$.

The map $D\mapsto G_D$ uses $3\mathrm{\mid }V\mathrm{\mid }$ vertices and at most $\mathrm{\mid }A\mathrm{\mid }+2\mathrm{\mid }V\mathrm{\mid }$ edges, so it is polynomial-time. Steps 2.2 and 3.1 prove $D$ has a directed Hamiltonian cycle if and only if $G_D$ has an undirected Hamiltonian cycle. By [L1], this is a polynomial-time many-one reduction.

Each of the four problems lies in $NP$: a certificate is an ordering of all vertices, and one checks in polynomial time that consecutive vertices are connected by the required edges or arcs, with one additional last-to-first check in the cycle cases.

By [L1], every $3$-CNF formula $\phi$ gives a digraph $D_{\phi }$ with distinguished vertices $s_{\phi },t_{\phi }$ such that $\phi$ is satisfiable exactly when $D_{\phi }$ has a directed Hamiltonian path from $s_{\phi }$ to $t_{\phi }$, and also a digraph $D_{\phi }^{\mathrm{\prime }}$ with a directed Hamiltonian cycle exactly when $\phi$ is satisfiable. Since [L3] makes $3$-SAT NP-complete, directed Hamiltonian cycle is NP-hard, and the endpoint-labelled problem ${\mathrm{D}\mathrm{H}\mathrm{A}\mathrm{M}\mathrm{P}\mathrm{A}\mathrm{T}\mathrm{H}}_{\ast }:=\{(D,s,t):D\text{ has a directed Hamiltonian path from }s\text{ to }t\}$ is NP-hard as well.

Reduce ${\mathrm{D}\mathrm{H}\mathrm{A}\mathrm{M}\mathrm{P}\mathrm{A}\mathrm{T}\mathrm{H}}_{\ast }$ to the ordinary directed Hamiltonian path problem. Given $(D,s,t)$, add fresh vertices $s_{-}$ and $t_{+}$ together with the two arcs $s_{-}\to s$ and $t\to t_{+}$. Any Hamiltonian path in the new digraph must start at $s_{-}$ and end at $t_{+}$, because $s_{-}$ has indegree $0$ and $t_{+}$ has outdegree $0$. Deleting those two new vertices therefore recovers a directed Hamiltonian path from $s$ to $t$ in $D$, and conversely any such path extends by adjoining $s_{-}$ at the front and $t_{+}$ at the end. Thus ordinary directed Hamiltonian path is NP-hard.

Next define the endpoint-labelled undirected problem ${\mathrm{U}\mathrm{H}\mathrm{A}\mathrm{M}\mathrm{P}\mathrm{A}\mathrm{T}\mathrm{H}}_{\ast }:=\{(G,s,t):G\text{ has an undirected Hamiltonian path from }s\text{ to }t\}\mathrm{.}$ First handle the allowed boundary case $s=t$. If $D$ has one vertex, map it to the one-vertex yes-instance with its sole vertex named as both endpoints. If $D$ has more than one vertex, no Hamiltonian ordering can both start and end at the same vertex, so map it to the fixed two-isolated-vertex no-instance. Now assume $s\mathrm{\ne }t$. Build an undirected graph $G^{\mathrm{\prime }}$ by replacing every vertex $v\mathrm{\notin }\{s,t\}$ by a path $v_1-v_2-v_3$, replacing $s$ by a single vertex $s_3$, replacing $t$ by a single vertex $t_1$, and adding an undirected edge $u_3-v_1$ for every arc $u\to v$ of $D$ that is not incoming to $s$ and not outgoing from $t$, with the conventions $u_3=s_3$ if $u=s$ and $v_1=t_1$ if $v=t$. A directed Hamiltonian path $s=v^{(1)}\to v^{(2)}\to \cdots \to v^{(r)}=t$ in $D$ then becomes the undirected Hamiltonian path $s_3,v_1^{(2)},v_2^{(2)},v_3^{(2)},\dots ,v_1^{(r-1)},v_2^{(r-1)},v_3^{(r-1)},t_1$ in $G^{\mathrm{\prime }}$. Conversely, an undirected Hamiltonian path from $s_3$ to $t_1$ must traverse every triple $v_1-v_2-v_3$ consecutively because the middle vertex $v_2$ has degree $2$, and all external edges join a $3$-vertex to a $1$-vertex. Contracting each triple therefore recovers a directed Hamiltonian path from $s$ to $t$ in $D$. Hence ${\mathrm{D}\mathrm{H}\mathrm{A}\mathrm{M}\mathrm{P}\mathrm{A}\mathrm{T}\mathrm{H}}_{\ast }{\le }_p{\mathrm{U}\mathrm{H}\mathrm{A}\mathrm{M}\mathrm{P}\mathrm{A}\mathrm{T}\mathrm{H}}_{\ast }$.

For undirected Hamiltonian cycle, NP-hardness is exactly [L2] composed with the NP-hardness of directed Hamiltonian cycle from step 1.2.

Reduce ${\mathrm{U}\mathrm{H}\mathrm{A}\mathrm{M}\mathrm{P}\mathrm{A}\mathrm{T}\mathrm{H}}_{\ast }$ to the ordinary undirected Hamiltonian path problem. Given $(G,s,t)$, attach two fresh leaves $s_{-}$ and $t_{+}$ by the edges $s_{-}s$ and $t{t}_{+}$. Any Hamiltonian path in the enlarged graph must have the two leaves as its endpoints, so deleting them recovers a Hamiltonian path from $s$ to $t$ in $G$; conversely any $s$-to-$t$ Hamiltonian path in $G$ extends by the two leaves. Therefore ordinary undirected Hamiltonian path is NP-hard.

Step 1.1 gives membership in $NP$, while steps 1.2, 2.1, 2.2, 2.3, and 3.1 give NP-hardness for directed Hamiltonian path, directed Hamiltonian cycle, undirected Hamiltonian path, and undirected Hamiltonian cycle. Hence all four problems are NP-complete by [L4].

By [L1] and [L2], it is enough to reduce INDEPENDENT SET to SUBSET SUM. If $k=0$, map $(G,k)$ to the fixed yes-instance consisting of the list $(1)$ with target $1$, because every graph has an independent set of size $0$. If $k>n$, map $(G,k)$ to the fixed no-instance consisting of the list $(1)$ with target $2$, because no graph on $n$ vertices has an independent set of size greater than $n$. So assume from now on that $1\le k\le n$. Set the base to $B:=n+2$.

For each vertex $v_i$, form a base-$B$ integer $a_i$ with $m+1$ digits: the leading digit is $1$, and the digit in edge-column $j$ is $1$ exactly when $e_j$ is incident to $v_i$. For each edge $e_j$, form one slack integer $b_j$ whose only nonzero digit is a $1$ in edge-column $j$. Let the target integer $T$ have leading digit $k$ and digit $1$ in every edge-column. Since the leading-column sum is at most $n<B$ and every edge-column sum is at most $3<B$, no carries can occur in any valid sum.

If $I\subseteq V(G)$ is an independent set of size $k$, choose the vertex numbers $a_i$ with $v_i\in I$. For each edge $e_j$ that has no endpoint in $I$, also choose the slack number $b_j$. Then the leading digit sums to $k$, and each edge-column sums to $1$: an edge with one endpoint in $I$ receives its $1$ from the corresponding vertex number, while an edge with no endpoint in $I$ receives its $1$ from its slack number. Hence the chosen integers sum to $T$.

Conversely, suppose that some subcollection of the constructed integers sums to $T$. Because the slack numbers have leading digit $0$, exactly $k$ vertex numbers $a_i$ must be chosen. Consider any edge $e_j=\{u,v\}$. The target has digit $1$ in column $j$, and there are no carries by step 2.1. Hence both endpoint numbers for $u$ and $v$ cannot both be chosen, because that would contribute at least $2$ in column $j$. Therefore the chosen $k$ vertices are pairwise nonadjacent, so they form an independent set.

The map in step 2.1 uses $n+m$ integers with $m+1$ base-$B$ digits, so its binary output size and construction time are polynomial in the size of $(G,k)$. Steps 3.1 and 3.2 prove a polynomial-time many-one reduction from INDEPENDENT SET to SUBSET SUM. Composing that reduction with [L1] and [L2] yields a polynomial-time many-one reduction from $3$-SAT to SUBSET SUM.

If $k>A$, map the instance to the one-element list $(1)$ for PARTITION. This is a correct no-instance because no subcollection of $a_1,\dots ,a_n$ can exceed the total $A$, and the list $(1)$ cannot be partitioned into two equal sums. Thus it remains to treat the case $k\le A$. Define $b:=2A-k$ and $c:=A+k$, and output the PARTITION instance with list $(a_1,\dots ,a_n,b,c)$.

The new total sum is $A+b+c=A+(2A-k)+(A+k)=4A$, so any equal partition must split the numbers into two subcollections each summing to $2A$.

If the SUBSET SUM instance is positive, choose $I\subseteq \{1,\dots ,n\}$ with ${\sum }_{i\in I}{a}_i=k$. Then ${\sum }_{i\in I}{a}_i+b=k+(2A-k)=2A$. The complementary numbers among $a_1,\dots ,a_n$ therefore sum to $A-k$, and $(A-k)+c=(A-k)+(A+k)=2A$. So the augmented list is a yes-instance of PARTITION.

Conversely, suppose the augmented list has a partition into two subcollections each summing to $2A$. The numbers $b$ and $c$ cannot lie on the same side because $b+c=3A>2A$, and they cannot both be absent from one side because then that side would use only the original $a_i$ and so would sum at most $A<2A$. Hence exactly one of $b,c$ lies on each side. The side containing $b$ must then contain original numbers summing to $2A-b=2A-(2A-k)=k$. Those numbers witness a yes-instance of SUBSET SUM.

The construction adds only two binary integers computed from $A$ and $k$, so it is polynomial-time. Steps 3.1 and 3.2 establish the required iff, and [L1] therefore gives a polynomial-time many-one reduction from SUBSET SUM to PARTITION.

Let the SET COVER universe be the edge set $U:=E$. For each vertex $v\in V$, define the subset $S_v:=\{e\in E:v\in e\}$. Output the SET COVER instance $(U,\{S_v:v\in V\},k)$. This is computable in polynomial time by scanning the incidence relation of $G$.

If $C\subseteq V$ is a vertex cover with $\mathrm{\mid }C\mathrm{\mid }\le k$, then every edge of $G$ has an endpoint in $C$. Equivalently, every element of $U=E$ lies in one of the sets $S_v$ with $v\in C$. Hence $\{S_v:v\in C\}$ is a set cover of size at most $k$.

Conversely, if $\{S_v:v\in C\}$ is a set cover of size at most $k$, then every edge $e\in E$ belongs to some $S_v$ with $v\in C$. By definition of $S_v$, that means $v$ is an endpoint of $e$. Therefore $C$ is a vertex cover of size at most $k$.

Steps 2.1 and 2.2 prove $(G,k)\in VERTEXCOVER⟺(U,\{S_v{\}}_{v\in V},k)\in SETCOVER$. By [L1], the construction in step 1.1 is a polynomial-time many-one reduction.

First reduce $\phi$ to a not-all-equal $3$-CNF formula. Introduce one global fresh variable $z$ and, for each clause $C_j=({\mathrm{\ell }}_{j1}\vee {\mathrm{\ell }}_{j2}\vee {\mathrm{\ell }}_{j3})$, one fresh variable $s_j$. Replace $C_j$ by the two NAE clauses $N_{j,1}=NAE({\mathrm{\ell }}_{j1},{\mathrm{\ell }}_{j2},s_j)$ and $N_{j,2}=NAE(\mathrm{\neg }{s}_j,{\mathrm{\ell }}_{j3},z)$. Call the conjunction of all these clauses $\psi$. This is polynomial-time and doubles the number of clauses.

The formula $\phi$ is satisfiable if and only if $\psi$ is NAE-satisfiable. If $\phi$ is satisfiable, set $z=0$ and keep the satisfying values of the original variables. Then every original clause has at least one true literal, so the four-tuple $({\mathrm{\ell }}_{j1},{\mathrm{\ell }}_{j2},{\mathrm{\ell }}_{j3},z)$ is not all equal; choose $s_j$ so that the pair of NAE clauses in step 1.1 holds, which is possible exactly because $NAE(a,b,c,d)⟺\mathrm{\exists }s(NAE(a,b,s)\wedge NAE(\mathrm{\neg }s,c,d))$. Conversely, if $\psi$ is NAE-satisfiable and $z=0$, then each original clause has at least one true literal and $\phi$ is satisfiable. If instead $z=1$, complement every Boolean value. NAE truth is invariant under global complementation, so the complemented assignment still satisfies $\psi$ and now has $z=0$. Thus $\phi$ is satisfiable in all cases.

From $\psi$, build a graph $G_{\psi }$ as follows. Add one distinguished vertex $\nu$. For each variable $u$ appearing in $\psi$, add the triangle on the three vertices $u,\mathrm{\neg }u,\nu$. For each NAE clause with ordered literal occurrences $(a,b,c)$, add a clause triangle with three position-distinguished vertices $(j,1),(j,2),(j,3)$, and join them respectively to the variable-triangle vertices labeled $a,b,c$. The position labels remain distinct even when a literal is repeated. This is polynomial-time and creates $O(\mathrm{\mid }\psi \mathrm{\mid })$ vertices and edges.

Suppose that $\psi$ is NAE-satisfiable. Colour $\nu$ by $2$. In each variable triangle, colour the literal vertices $u$ and $\mathrm{\neg }u$ by their Boolean values $0$ and $1$, which are opposite because they are complements. Now fix one clause triangle. Because the clause is NAE-satisfied, two of its literals have different Boolean values; colour the corresponding two clause vertices by the opposite Boolean values, so each differs from the colour of the adjacent variable vertex. Colour the third clause vertex by $2$. The three clause-vertex colours are then $0,1,2$, so the clause triangle is proper. Doing this for every clause yields a proper three-colouring of $G_{\psi }$.

Suppose conversely that $G_{\psi }$ has a proper three-colouring. Every triangle uses all three colours, so after permuting colour names assume $\nu$ has colour $2$. In each variable triangle, the vertices $u$ and $\mathrm{\neg }u$ therefore receive colours $0$ and $1$ in some order; assign the truth value of the literal to be the complementary Boolean value, so $u$ and $\mathrm{\neg }u$ receive opposite truth values. In each clause triangle, exactly one vertex has colour $2$ and the other two have colours $0$ and $1$. Because each clause vertex is adjacent to the matching literal vertex, a clause vertex with colour $0$ or $1$ forces the corresponding literal to have the complementary truth value. Thus the three literals of the clause are not all equal, so the clause is NAE-satisfied. Therefore $\psi$ is NAE-satisfiable.

Steps 2.1, 3.1, and 4.1 show $\phi \in 3\text{-}SAT⟺\psi \text{ is NAE-satisfiable }⟺G_{\psi }\in 3\text{-}COLORABILITY$. Since the constructions in steps 1.1 and 2.2 are polynomial-time, [L1] and [L2] yield a polynomial-time many-one reduction from $3$-SAT to $3$-COLORABILITY.

Define the constant map $f(x):=y_B$ for every source instance $x$. This map is total and polynomial-time, and it certainly sends every yes-instance of $A$ to a yes-instance of $B$.

Let $x_0\mathrm{\notin }A$. Then $f(x_0)=y_B\in B$, so the reverse implication in [L2] fails: $f(x_0)\in B$ does not force $x_0\in A$. Therefore yes-preservation alone does not make $f$ a correct many-one reduction.

The statement is false.

Consider the one-number SUBSET SUM instances $([2^m],2^m)$ for $m\ge 1$. By [F1], the binary input length is $O(m)$.

The standard table-filling algorithm uses $\mathrm{\Theta }(nT)=\mathrm{\Theta }(2^m)$ time on this family because here $n=1$ and $T=2^m$.

Since $2^m$ is exponential in the binary length $m$, the running time in step 2.1 is not polynomial in the input length. By [L1], polynomial-time complexity is measured against that binary length. Therefore pseudopolynomial dependence on $T$ does not imply polynomial dependence on the bit-length of $T$.

The statement is false.