Relating Partial and Complete Solutions and the Complexity of Computing Smallest Solutions

摘要

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 Gal et al. We establish 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 Δ_2~p-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 ≠ NP. We discuss this application to non-self-reducibility and provide a general related result.