# Has anyone found polynomial algorithm on Hamiltonian cycle isomorphism?

As the title says, has anyone found a polynomial time algorithm for checking whether two graphs having a Hamiltonian cycle are isomorphic? Is this problem NP-complete?

• Definitely No, for Directed graphs at least. Because the Best Algorithm for Tournament isomorphism takes $O(n^{\log{n}})$. And Tournaments are the graphs with Hamiltonian paths. Refer to uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.190/Mitarbeiter/… – rizwanhudda Jun 15 '12 at 17:23
• @rizwanhudda Thank you very much. May I ask you one more question? Is this problem NP-complete? – Leo Sanchez Jun 15 '12 at 22:22
• Also, what about cycles? – Leo Sanchez Jun 15 '12 at 22:26
• I don't know any results about hamiltonian cycle. But, this problem can't be NP-Complete as it is a special case of Graph Isomorphism. And Graph Isomorphism isn't known to be NP-Complete. – rizwanhudda Jun 16 '12 at 0:37
• As rizwanhudda said, this problem is a special case of the graph isomorphism problem and therefore it is not known to be NP-complete. We cannot say “this problem can’t be NP-complete” because of that, because the graph isomorphism problem might be NP-complete. However, many complexity theorists believe that the graph isomorphism problem is not NP-complete (and therefore they will believe that your problem is not NP-complete, either) because the NP-completeness of the graph isomorphism problem would contradict the conjecture called “the polynomial hierarchy does not collapse.” – Tsuyoshi Ito Jun 17 '12 at 20:35

Given two graphs $G_1 = (V_1,E_1)$ and $G_2 = (V_2,E_2)$, $|V_1| = |V_2|=n$, expand $G_1$ with a complete graph $K_{2n}$ labeling its nodes in pairs $(a_i, b_i)$; then for each vertex $u_i \in |V_1|$ add two edges $(a_i,u_i)$ and $(u_i,b_i)$ that connect $G_1$ to the $K_{2n}$. Expand $G_2$ in the same way.
By construction the two expanded graphs $G'_1$ and $G'_2$ have an Hamiltonian cycle $(a_1 u_1 b_1 a_2 u_2 b_2 ... a_n u_n b_n a_1)$ and the original graphs are isomorphic iff $G'_1$ and $G'_2$ are isomorphic. Informally: in $G'_1$ and $G'_2$ the added nodes cannot "interfere" with the original isomorphism because their degree is greater than $\max(\text{deg}(u_i))$