| 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,
|