Title Relating Partial and Complete Solutions and the Complexity of Computing Smallest Solutions Authors Andre Grosse, Institut fuer Informatik, Friedrich-Schiller-Universitaet Jena Joerg Rothe, Mathematisches Institut, Heinrich-Heine-Universitaet Duesseldorf Gerd Wechsung, Institut fuer Informatik, Friedrich-Schiller-Universitaet 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 four-coloring for planar graphs is P^{NP}-hard. This result optimally improves upon a result of Khuller and Vazirani who prove this problem to be NP-hard and conclude that it is not self-reducible in the sense of Schnorr, assuming P differs from NP. We discuss this application to non-self-reducibility and provide a general related result. Keywords: Computational complexity, graph isomorphism problem, self-reducibility.