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 }$. Consider the first departure from traversal of successive crossbars in one direction, with optional same-pair clause detours. Until such a departure, the preceding crossbar vertices have been visited and the succeeding ones have not. One possible departure would exit directly to $q_i$ from the same end that was just entered from $p_i$. This leaves the opposite end unvisited; its only later possible entry is from its crossbar neighbor, after which its exits to that neighbor and to the already visited $q_i$ are blocked. This is impossible. Every other possible departure is an arc to a clause vertex $c_j$: all other available unvisited successors continue the crossbar or its prescribed gadget connector. If the departure is from the first endpoint of its pair and does not return to the second endpoint, that second endpoint remains unvisited. Its only neighbors are its visited mate, the clause vertex just visited, and its next crossbar neighbor. It can later be entered only from the last of these, after which every exit goes to a visited vertex, although it is not $t_{\phi }$. If instead the departure is from the second endpoint after its mate has already been visited, its next crossbar separator remains unvisited. An interior separator has only its two crossbar neighbors; entering it later from the other neighbor again leaves no unvisited exit. For a separator at the far end, its only possible incoming arcs are from the departed endpoint and $p_i$, both already visited with their successors fixed, so it cannot be entered later at all. These arguments are unchanged on reversing left and right and also cover clauses containing both signs of a variable. Consequently no first departure exists. Thus every clause visit is a same-pair detour, the gadgets are traversed in order, and each entire crossbar is traversed monotonically. Set $x_i=true$ exactly for a left-to-right traversal. The detour through every clause vertex has the orientation of a literal made true by this assignment, so every clause is satisfied.

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.