[proofplan] We prove NP-completeness by verifying membership in NP and then giving a polynomial-time many-one reduction from the directed Hamiltonian cycle problem. The reduction replaces each vertex of a directed graph by a three-vertex path and replaces each directed arc by an undirected edge from the source gadget's exit to the target gadget's entrance. The internal degree-two vertex in each gadget forces any undirected Hamiltonian cycle to pass through the gadget as a block, so the undirected cycle records a directed Hamiltonian cycle in the original graph. [/proofplan] [step:Verify that a Hamiltonian cycle certificate can be checked in polynomial time] Let $\mathrm{HAM}\text{-}\mathrm{CYCLE}$ denote the language of finite undirected simple graphs $G = (V,E)$ with $|V| \geq 3$ for which there exists a cycle visiting every vertex of $V$ exactly once. A certificate for $G \in \mathrm{HAM}\text{-}\mathrm{CYCLE}$ is an ordered list $(v_1,\dots,v_n)$ of the vertices of $G$, where $n = |V|$. The verifier checks that every element of $V$ appears exactly once in the list and that $\{v_i,v_{i+1}\} \in E$ for each $1 \le i < n$, and also $\{v_n,v_1\} \in E$. These checks require at most polynomial time in the standard adjacency-list or adjacency-matrix encoding of $G$. Hence $\mathrm{HAM}\text{-}\mathrm{CYCLE} \in \mathrm{NP}$. [/step] [step:Reduce directed Hamiltonian cycle to undirected Hamiltonian cycle] Let $\mathrm{DIR}\text{-}\mathrm{HAM}\text{-}\mathrm{CYCLE}$ denote the language of finite directed graphs $D=(V,A)$ containing a directed cycle that visits every vertex of $V$ exactly once. We use the standard theorem that $\mathrm{DIR}\text{-}\mathrm{HAM}\text{-}\mathrm{CYCLE}$ is NP-complete. It remains to give a polynomial-time map $R$ from directed graphs to undirected graphs such that \begin{align*} D \in \mathrm{DIR}\text{-}\mathrm{HAM}\text{-}\mathrm{CYCLE} \iff R(D) \in \mathrm{HAM}\text{-}\mathrm{CYCLE}. \end{align*} Define $R$ as follows. For each vertex $v \in V$, introduce three vertices $v_{\mathrm{in}}$, $v_{\mathrm{mid}}$, and $v_{\mathrm{out}}$. Add the two internal undirected edges $\{v_{\mathrm{in}},v_{\mathrm{mid}}\}$ and $\{v_{\mathrm{mid}},v_{\mathrm{out}}\}$. For each directed arc $(u,v) \in A$, add the undirected edge $\{u_{\mathrm{out}},v_{\mathrm{in}}\}$. Let $G = R(D)$ be the resulting undirected graph. The construction creates $3|V|$ vertices and $2|V|+|A|$ edges, so $R$ is computable in polynomial time. [guided] We reduce from the directed Hamiltonian cycle problem because direction can be encoded locally. The gadget for a vertex $v$ is the path \begin{align*} v_{\mathrm{in}} - v_{\mathrm{mid}} - v_{\mathrm{out}}. \end{align*} The middle vertex $v_{\mathrm{mid}}$ has exactly two neighbours in $G$, namely $v_{\mathrm{in}}$ and $v_{\mathrm{out}}$. Therefore any Hamiltonian cycle of $G$ must use both internal edges incident to $v_{\mathrm{mid}}$. This forces the cycle to traverse the whole gadget as one consecutive block, either from $v_{\mathrm{in}}$ to $v_{\mathrm{out}}$ or from $v_{\mathrm{out}}$ to $v_{\mathrm{in}}$. The external edges encode the arcs of $D$: for every directed arc $(u,v) \in A$, the construction adds exactly one edge connecting the exit $u_{\mathrm{out}}$ of the $u$-gadget to the entrance $v_{\mathrm{in}}$ of the $v$-gadget. Thus a traversal that leaves $u$ through $u_{\mathrm{out}}$ and enters $v$ through $v_{\mathrm{in}}$ records the directed move $u \to v$. The graph $G$ has $3|V|$ vertices and $2|V|+|A|$ edges, so writing down all vertices and edges of $G$ takes polynomial time in the size of the directed input graph $D$. [/guided] [/step] [step:Turn a directed Hamiltonian cycle into an undirected Hamiltonian cycle] Suppose $D$ has a directed Hamiltonian cycle \begin{align*} v_1 \to v_2 \to \cdots \to v_n \to v_1, \end{align*} where $V=\{v_1,\dots,v_n\}$. In $G=R(D)$, each arc $(v_i,v_{i+1})$ with $1 \le i < n$ gives the edge $\{(v_i)_{\mathrm{out}},(v_{i+1})_{\mathrm{in}}\}$, and the arc $(v_n,v_1)$ gives the edge $\{(v_n)_{\mathrm{out}},(v_1)_{\mathrm{in}}\}$. Therefore the cyclic ordering \begin{align*} (v_1)_{\mathrm{in}}, (v_1)_{\mathrm{mid}}, (v_1)_{\mathrm{out}}, (v_2)_{\mathrm{in}}, (v_2)_{\mathrm{mid}}, (v_2)_{\mathrm{out}}, \dots, (v_n)_{\mathrm{in}}, (v_n)_{\mathrm{mid}}, (v_n)_{\mathrm{out}} \end{align*} uses only edges of $G$ and visits each vertex of $G$ exactly once. Hence $G$ has a Hamiltonian cycle. [/step] [step:Extract a directed Hamiltonian cycle from an undirected one] Conversely, suppose $G=R(D)$ has a Hamiltonian cycle $C$. For each $v \in V$, the vertex $v_{\mathrm{mid}}$ has degree exactly $2$ in $G$, with neighbours $v_{\mathrm{in}}$ and $v_{\mathrm{out}}$. Since $C$ is a Hamiltonian cycle, both edges of $C$ incident to $v_{\mathrm{mid}}$ must be $\{v_{\mathrm{in}},v_{\mathrm{mid}}\}$ and $\{v_{\mathrm{mid}},v_{\mathrm{out}}\}$. Thus the three vertices $v_{\mathrm{in}},v_{\mathrm{mid}},v_{\mathrm{out}}$ occur consecutively on $C$. Choose either orientation of the undirected cycle $C$. If necessary, reverse this orientation so that one selected gadget is traversed from its entrance to its exit. Because every external edge of $G$ joins some $u_{\mathrm{out}}$ to some $v_{\mathrm{in}}$, the consecutive-block condition forces every gadget to be traversed in the same entrance-to-exit direction under this orientation; otherwise an external edge would have to join two entrances or two exits, and no such edge exists in $G$. Contract each consecutive block $v_{\mathrm{in}},v_{\mathrm{mid}},v_{\mathrm{out}}$ to the original vertex $v$. The external edges of $C$ then give directed arcs $(u,v) \in A$ linking the contracted vertices in a cyclic order that visits every vertex of $V$ exactly once. Hence $D$ has a directed Hamiltonian cycle. [/step] [step:Conclude NP-completeness by polynomial-time many-one reduction] The map $R$ is polynomial-time computable and satisfies \begin{align*} D \in \mathrm{DIR}\text{-}\mathrm{HAM}\text{-}\mathrm{CYCLE} \iff R(D) \in \mathrm{HAM}\text{-}\mathrm{CYCLE}. \end{align*} Since $\mathrm{DIR}\text{-}\mathrm{HAM}\text{-}\mathrm{CYCLE}$ is NP-complete, this equivalence shows that $\mathrm{HAM}\text{-}\mathrm{CYCLE}$ is NP-hard under polynomial-time many-one reductions. Together with $\mathrm{HAM}\text{-}\mathrm{CYCLE} \in \mathrm{NP}$ proved above, this establishes that $\mathrm{HAM}\text{-}\mathrm{CYCLE}$ is NP-complete. [/step]