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.