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$
6
  • 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$ Jun 15, 2012 at 17:23
  • $\begingroup$ @rizwanhudda Thank you very much. May I ask you one more question? Is this problem NP-complete? $\endgroup$ Jun 15, 2012 at 22:22
  • $\begingroup$ Also, what about cycles? $\endgroup$ Jun 15, 2012 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$ Jun 16, 2012 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$ Jun 17, 2012 at 20:35

2 Answers 2

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$
2
  • $\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$ Oct 8, 2012 at 14:40
  • $\begingroup$ Well, I think this answer should be updated now that GI is known to be quasi-polynomial. $\endgroup$ Jul 21, 2016 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 and acknowledge you have read our privacy policy.

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