Co-NP-completeness of minimal TSP tour? This problem came out of my recent blog post, suppose you are given a TSP tour, is it co-NP-complete to determine if it is a minimal one?

More precisely is the following problem NP-complete:

Instance: Given a complete graph G with edges weighted with positive integers and a simple cycle C that visits all the nodes of G.

Question: Is there a simple cycle D that visits all the nodes of G such that the total weight of all the edges of D in G is strictly less than the total weight of all the edges of C in G?
A sketch of a possible reduction to prove that it is NP-complete.

Informally it starts from a modified 3SAT formula used to show that 3SAT is ASP-complete (Another Solution Problem), and "follows" the standard chain of reductions 3SAT=>DIRECTED HAMCYCLE => UNDIRECTED HAMCYCLE => TSP


Start with a 3SAT formula $\varphi$ with $n$ variables $x_1,...x_n$ and $m$ caluses $C_1,...,C_m$;
Trasform it to a new formula $\varphi'$ adding a new variable $t$ ...;
... and expanding each clause $(x_{i_1} \lor x_{i_2} \lor x_{i_3})$ to $(x_{i_1} \lor x_{i_2} \lor x_{i_3} \lor t)$;
From $\varphi'$ build the diamonds structure graph $G = \{V,E\}$ used to prove that DIRECTED HAMILTONIAN CYCLE is NP-Complete; suppose that each clause $C_j$ correspond to node $N_j$ in $G$;
Modify $G$ into graph $G' = \{V',E'\}$ replacing each node $u$ with three linked nodes $u_1, u_2, u_3$  and modify the edges according to the standard reduction used to prove the NP-completeness of UNDIRECTED HAMILTONIAN CYCLE from DIRECTED HAMILTONIAN CYCLE i.e. $u_1$ is the node used for incoming edges, $u_3$ is the node used for outgoing edges; 
Convert the UNDIRECTED HAMILTONIAN CYCLE instance on $G'$ to a TSP instance $T$ in which all edges of $G'$ has weight $w = 1$, except the (unique) edge in the diamond going to the "positive" assignment of $t$ which has weight $w = 2$ (red edge in the figure below); finally the edges added to make $G'$ complete have weight $w = 3$.


Clearly the TSP instance $T$ has a simple cycle that visits all nodes which corresponds to the satisfying assignment of  $\varphi'$ in which $t = true$ (and this tour can be easily constructed in polynomial time), but it has total weight $|V'|+1$ (because it uses the edge that correspond to the assignment $t = true$ that has weight 2). $T$ has another simple cycle that visits all nodes with a lower total weight $|V'|$ if and only if the edge of weight $2$ that corresponds to the assignment $t = true$ is not used; or equivalently if and only if there is another satisfying assignment of $\varphi'$ in which
$t = false$ ; but this can be true if and only if the original formula $\varphi$ is satisfiable.

I'll think more about it, and I'll write a formal proof (if it doesn't turn out to be wrong :-).
Let me know if you need further details about one or more of the above passages.



As noted by domotorp an interesting consequence is that the following problem is NP-complete: Given a graph $G$ and an Hamiltonian path in it, does $G$ have an Hamiltonian cycle?