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?

up vote 17 down vote accepted

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

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?

  • 4
    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
  • 1
    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
  • 2
    arxiv.org/pdf/1403.3431.pdf by Marzio De Biasi – Brout 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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.