<p><a href="http://epubs.siam.org/doi/abs/10.1137/0206005">Papadimitriou &amp; Steiglitz (1977)</a> have shown NP-completeness of this problem.</p>

CC BY-SA 3.0
2014-03-20T14:25:15.287Z
Ouch ... I have a slight "reinveting-the-wheel" feeling :-) The paper is behind SIAM paywall, is the proof similar to mine?
Marzio De Biasi
CC BY-SA 3.0
2014-03-20T15:08:49.487Z
I don't have access to the paper, but you can find the proofs also in Section 19.9 of [their book](http://www.amazon.com/Combinatorial-Optimization-Algorithms-Complexity-Computer/dp/0486402584), which may be more accessible.
Marcus Ritt
CC BY-SA 3.0
2014-03-20T16:08:42.693Z
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
CC BY-SA 3.0
2014-03-21T12:00:45.493Z
@Marzio de Biasi I think updating the paper is fine. Your alternative proof is still interesting.
Marcus Ritt
CC BY-SA 3.0
2014-03-20T13:30:25.480Z
2014-03-20T13:30:25.480Z
Marcus Ritt
<p>A sketch of a possible reduction to prove that it is NP-complete.</p>

<p>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</p>

<ul>
<li>Start with a 3SAT formula $\varphi$ with $n$ variables $x_1,...x_n$ and $m$ caluses $C_1,...,C_m$;</li>
<li>Trasform it to a new formula $\varphi'$ adding a new variable $t$ ...;</li>
<li>... 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)$;</li>
<li>From $\varphi'$ build the <em>diamonds structure</em> 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$;</li>
<li>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; </li>
<li>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$.</li>
</ul>

<p>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.</p>

<p>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.</p>

<p><img src="https://i.sstatic.net/ZBDcx.png" alt="enter image description here"></p>

<p>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?</p>

CC BY-SA 3.0
2014-01-10T19:46:55.673Z
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
CC BY-SA 3.0
2014-01-10T22:00:03.583Z
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
CC BY-SA 3.0
2014-01-11T07:59:54.620Z
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
CC BY-SA 3.0
2014-01-11T08:07:23.777Z
@domotorp: you're right! :)
Marzio De Biasi
CC BY-SA 3.0
2014-03-21T11:18:18.237Z
http://arxiv.org/pdf/1403.3431.pdf by Marzio De Biasi
Turbo
CC BY-SA 3.0
2014-03-21T11:25:38.407Z
@J.A: the latest "reinventing the wheel" version can be [downloaded here](http://www.nearly42.org/vdisk/cstheory/tspmindecision.pdf) (it will appear on arXiv today or next monday)  :-) :-). I will update the answer and include the latest arXiv link.
Marzio De Biasi
CC BY-SA 3.0
2014-01-10T17:20:07.023Z
2014-01-11T14:22:47.667Z
2014-01-11T14:22:47.667Z
Marzio De Biasi
<p>This problem came out of my recent <a href="http://blog.computationalcomplexity.org/2014/01/is-traveling-salesman-np-complete.html">blog post</a>, suppose you are given a TSP tour, is it co-NP-complete to determine if it is a minimal one?</p>

<p>More precisely is the following problem NP-complete:</p>

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

<p>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?</p>

<np-hardness>
Co-NP-completeness of minimal TSP tour?
Lance Fortnow
# Co-NP-completeness of minimal TSP tour?

(Asked by: username_0 on 2014-01-10)

This problem came out of my recent [blog post](http://blog.computationalcomplexity.org/2014/01/is-traveling-salesman-np-complete.html), 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?

**Tags:** np-hardness

---

## 2 answers

### Answer by username_2 on 2014-01-10. Score: 17 | Accepted answer

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.

![enter image description here](https://i.sstatic.net/ZBDcx.png)

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?

> **Comments:**
> **username_3**: 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?  
> **username_0**: 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.  
> **username_3**: 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.  
> **username_2**: @domotorp: you're right! :)  
> **username_4**: http://arxiv.org/pdf/1403.3431.pdf by Marzio De Biasi  
> **username_2**: @J.A: the latest "reinventing the wheel" version can be [downloaded here](http://www.nearly42.org/vdisk/cstheory/tspmindecision.pdf) (it will appear on arXiv today or next monday)  :-) :-). I will update the answer and include the latest arXiv link.  

---

### Answer by username_1 on 2014-03-20. Score: 5

[Papadimitriou & Steiglitz (1977)](http://epubs.siam.org/doi/abs/10.1137/0206005) have shown NP-completeness of this problem.

> **Comments:**
> **username_2**: Ouch ... I have a slight "reinveting-the-wheel" feeling :-) The paper is behind SIAM paywall, is the proof similar to mine?  
> **username_1**: I don't have access to the paper, but you can find the proofs also in Section 19.9 of [their book](http://www.amazon.com/Combinatorial-Optimization-Algorithms-Complexity-Computer/dp/0486402584), which may be more accessible.  
> **username_2**: 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?  
> **username_1**: @Marzio de Biasi I think updating the paper is fine. Your alternative proof is still interesting.  

---

