NPC Pills (NP-Complete pills) is a collection of some NP-completeness proofs that I posted on the Q&A sites cstheory.stackexchange.com and cs.stackexchange.com. Up to my knowledge they are original and some of them are not so trivial. At present, most of them are just sketches that contain the NP-hardness reduction idea, but for some of them I wrote (or I’m going to write) a more formal paper. If you are particularly interested in one of them write me an email.
NPC Pill #2: Minimal TSP Tour is coNP-Complete
The Traveling Salesman Problem (TSP) is a well–known problem from graph theory: we are given $n$ cities and a nonnegative integer distance $d_{ij}$ between any two cities $i$ and $j$ (assume that the distances are symmetric, i.e. for all $i,j, d_{ij} = d_{ji}$). We are asked to find the shortest tour of the cities, that is a permutation $\pi$ of $[1..n]$ such that
$\sum_{i=1}^n d_{\pi(i),\pi(i+1)}$ (where $\pi(n+1) = \pi(n)$) is as small as possible. Its well-known NP-complete version is the following (TSPDECISION): If a nonnegative integer bound $B$ (the traveling salesman’s “budget”) is given along with the distances, does there exist a tour of all the cities having total length no more than $B$?
But what about checking that a tour has effectively minimal length? We prove that the problem:
TSPMINDECISION: Given a set of $n$ cities, the distance between all city pairs and a tour $T$, is T visiting each city exactly once and is T of minimal length?
is coNP-complete. As a secondary result we prove that given a graph $G$ and an Hamiltonian path, it is NP-complete to check if $G$ contains an Hamiltonian cycle as well.
UPADTE 2014-03-21: after publishing the proof on arXiv, it turned out that the same result was proved Papadimitriou and Steiglitz in [1] (see also [2] Section 19.9). Our proof is slightly different and it may be interesting in and of itself, so we decided not to withdraw the paper.
[1] Christos H. Papadimitriou and Kenneth Steiglitz. 1982. Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Inc., Upper Saddle River, NJ, USA.
[2] Christos H. Papadimitriou and Kenneth Steiglitz. On the Complexity of Local Search for the Traveling Salesman Problem. SIAM J. Comput., 6(1), 76–83, 1977.