Computing Complete Graph Isomorphisms and Hamiltonian Cycles from Partial Ones

2001/06/19 by Grosse, André, Rothe, Joerg, Wechsung, Gerd
#Computational Complexity (cs.CC) #F.1.3 #F.2.2 #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.cs/0106041

Abstract

We prove that computing a single pair of vertices that are mapped onto each other by an isomorphism ϕ between two isomorphic graphs is as hard as computing ϕ itself. This result optimally improves upon a result of Gál et al. We establish a similar, albeit slightly weaker, result about computing complete Hamiltonian cycles of a graph from partial Hamiltonian cycles.

Related

• Testing Isomorphism of Graphs in Polynomial Time
• A Polynomial Time Algorithm for Graph Isomorphism
• The direct algorithm for solving of the graph isomorphism problem
• The Graph Isomorphism Problem and approximate categories
• On the solution of the Graph Isomorphism Problem Part 1