Title  Relating Partial and Complete Solutions and the Complexity of Computing Smallest Solutions 
Authors  Andre Grosse, Institut fuer Informatik,
FriedrichSchillerUniversitaet Jena
Joerg Rothe, Mathematisches Institut, HeinrichHeineUniversitaet Duesseldorf Gerd Wechsung, Institut fuer Informatik, FriedrichSchillerUniversitaet Jena 
Main Fields  4. computational complexity 
Other Main Fields  
Abstract + Keywords  We prove that computing a single pair
of vertices that are mapped
onto each other by an isomorphism $\phi$ between two isomorphic graphs is as hard as computing $\phi$ itself. This result optimally improves upon a result of Gal, Halevi, Lipton, and Petrank. We obtain a similar, albeit slightly weaker, result about computing complete Hamiltonian cycles of a graph from partial Hamiltonian cycles. We also show that computing the lexicographically first fourcoloring for planar graphs is P^{NP}hard. This result optimally improves upon a result of Khuller and Vazirani who prove this problem to be NPhard and conclude that it is not selfreducible in the sense of Schnorr, assuming P differs from NP. We discuss this application to nonselfreducibility and provide a general related result. Keywords: Computational complexity,
graph isomorphism problem,
