Minimal TSP Tour is coNP-Complete
classification
💻 cs.CC
keywords
hamiltonianproblemconp-completecycleminimalproofreductiontour
pith:TUTJC5VM Add to your LaTeX paper
What is a Pith Number?\usepackage{pith}
\pithnumber{TUTJC5VM}
Prints a linked pith:TUTJC5VM badge after your title and writes the identifier into PDF metadata. Compiles on arXiv with no extra files. Learn more
read the original abstract
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).
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.