2014/03/13 by Marzio De Biasi, De Biasi, Marzio
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Formal Methods in Verification #cs.CC
paper · pdf · doi:10.48550/arxiv.1403.3431
5 pages, 1 figure
arxiv created 2014/03/21 · arxiv updated 2014/03/24
The problem of deciding if a Traveling Salesman Problem (TSP) tour is minimal was proved to be coNP-complete by Papadimitriou and Steiglitz. We give an alternative proof based on a polynomial time reduction from 3SAT. Like the original proof, our reduction also shows that given a graph G and an Hamiltonian path of G, it is NP-complete to check if G contains an Hamiltonian cycle (Restricted Hamiltonian Cycle problem).