7
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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/… $\endgroup$ – rizwanhudda Jun 15 '12 at 17:23
  • $\begingroup$ @rizwanhudda Thank you very much. May I ask you one more question? Is this problem NP-complete? $\endgroup$ – Leo Sanchez Jun 15 '12 at 22:22
  • $\begingroup$ Also, what about cycles? $\endgroup$ – Leo Sanchez Jun 15 '12 at 22:26
  • 4
    $\begingroup$ 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. $\endgroup$ – rizwanhudda Jun 16 '12 at 0:37
  • 9
    $\begingroup$ 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.” $\endgroup$ – Tsuyoshi Ito Jun 17 '12 at 20:35
7
$\begingroup$

What follows is taken from Tsuyoshi Ito's comment.

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

$\endgroup$
  • $\begingroup$ Please do not feel obligated to mark an answer as a community wiki just because it is a copy of my comment, in case you or anyone else feels so. $\endgroup$ – Tsuyoshi Ito Oct 8 '12 at 14:40
  • $\begingroup$ Well, I think this answer should be updated now that GI is known to be quasi-polynomial. $\endgroup$ – Guillermo Angeris Jul 21 '16 at 17:16
4
$\begingroup$

As suggested by Kaveh, perhaps this is a reduction that can prove that the class of graphs with an Hamiltonian cycle is GI-complete.

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))$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.