# 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?

• So you essentially show that given a graph and a H-path in it, it is NPc to decide whether it has a H-cycle, right? – domotorp Jan 10 '14 at 19:46
• Looks great. Thanks for putting in the effort in the write up. A few changes to directly address my question: The edges of the graph should be weighted 1 except for that special edge which should be weighted 2 and the non-edges should be weighted 3. – Lance Fortnow Jan 10 '14 at 22:00
• If you delete that specific edge from $G$, then $H_1$ becomes a H-path and $H_2$ would remain a H-cycle, so you essentially do show what I wrote, right? For me this statement looks more interesting than the original question. – domotorp Jan 11 '14 at 7:59
• @domotorp: you're right! :) – Marzio De Biasi Jan 11 '14 at 8:07
• arxiv.org/pdf/1403.3431.pdf by Marzio De Biasi – T.... Mar 21 '14 at 11:18

Papadimitriou & Steiglitz (1977) have shown NP-completeness of this problem.

• Ouch ... I have a slight "reinveting-the-wheel" feeling :-) The paper is behind SIAM paywall, is the proof similar to mine? – Marzio De Biasi Mar 20 '14 at 14:25
• I don't have access to the paper, but you can find the proofs also in Section 19.9 of their book, which may be more accessible. – Marcus Ritt Mar 20 '14 at 15:08
• Ok thanks! The proof is different (they modify an instance $G$ of Hamiltonian circuit problem into $G'$ that always has an Hamiltonian path but has an Hamiltonian circuit if and only if $G$ has an Hamiltonian circuit). But I must update the paper I posted to arXiv and aknowledge that it is not a new result (or delete it). What do you think? – Marzio De Biasi Mar 20 '14 at 16:08
• @Marzio de Biasi I think updating the paper is fine. Your alternative proof is still interesting. – Marcus Ritt Mar 21 '14 at 12:00