patternMinor
Has anyone found polynomial algorithm on Hamiltonian cycle isomorphism?
Viewed 0 times
anyonecyclehamiltonianpolynomialhasfoundalgorithmisomorphism
Problem
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?
Solution
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.”
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.”
Context
StackExchange Computer Science Q#2383, answer score: 7
Revisions (0)
No revisions yet.