Directed and undirected Hamiltonian path and cycle are NP-complete

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].