Re: Discussion about transformation TSP to UniqueTSP

tchow@xxxxxxxxxxxxx wrote:
In article <456c6df5$0$568$b45e6eb0@xxxxxxxxxxxxxxxxxxxxxxxxx>, I wrote:
In article <1164714136.832964.38370@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
deepakc <deepakc@xxxxxxxxxxxxxxxx> wrote:
Could U pls advise whether this Question for the TSP is also
NP-Complete: -
"Does there exist a TSP tour of length = C ??"
This problem is usually called the EXACT TSP problem.

Gerhard Woeginger pointed out to me by email that I goofed here. EXACT
TSP is the question of whether the *optimal* tour has length = C. I also
incorrectly said:

DP is contained in NP, of course

I meant to say that NP is contained in DP. Showing that DP is contained
in NP would, among other things, show that NP = co-NP.

Getting back to your question, it is certainly in NP, and I think it is
NP-complete, but I don't see immediately how to prove that.

I think Deepakc was right, before he corrected himself, that
we can reduce Hamiltonian-Circuit to the problem at issue. Give
all the edges cost one, then add all possible edges assigning cost
greater than the number of nodes, call it N nodes. The resulting
graph has a tour of cost N-1 iff the original had a Hamiltonian
Circuit.

Since it's in NP and we can reduce HC to it, it's NP-Complete.

Am I missing anything?

--
--Bryan
.

Relevant Pages