Reduce the
DIRECTED HAMILTONIAN CIRCUIT problem to the
UNDIRECTED HAMILTONIAN CIRCUIT problem.
These problems are defined as follows:
- DIRECTED HAMILTONIAN CIRCUIT: given a directed graph $G$, is there a
directed cycle that visits each node of $G$ exactly once? In other words, is it
possible to order the nodes of $G$ such that there is an edge from each node to
the following node in the list and an edge from the last node to the first
node?
More formally, this problem can be defined as the following set:
$\{ G=\langle V,E\rangle \mid V=\{n_1,\ldots,n_k\}\;\wedge\;\forall i\in\{1,\ldots,k\}: \langle n_i,n_{(i\text{ mod }k)+1}\rangle\in E \}$
- UNDIRECTED HAMILTONIAN CIRCUIT: given an undirected graph $G$, is
there a cycle that visits each node of $G$ exactly once? In other words, is it
possible to order the nodes of $G$ such that there is an edge between each $2$
contiguous nodes and an edge between the last and the first nodes?
More formally, this problem can be defined as the following set:
$\{ G=\langle V,E\rangle \mid V=\{n_1,\ldots,n_k\}\;\wedge\;\forall i\in\{1,\ldots,k\}: \{n_i,n_{(i\text{ mod }k)+1}\}\in E \}$
The input and output of the reduction conform to the following data types: