3SAT polynomial-time many-one reduces to directed Hamiltonian cycle

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.