Re: Discussion about transformation TSP to UniqueTSP


deepakc napisal(a):
tchow@xxxxxxxxxxxxx wrote:
--
Tim Chow tchow-at-alum-dot-mit-dot-edu

Tim,

Could U pls advise whether this Question for the TSP is also
NP-Complete: -
"Does there exist a TSP tour of length = C ??"

I have checked many references on Google, but they do not mention about
the "only =" version. They only state that " < = " version is
NP-Complete, i.e. "Does there exist a TSP tour of length <= C ??"

If you know any "strong" references stating that the "only =" version
Question is also NP-Complete, could you please let us know.

By strong, I mean something from some very reputed Journal, or some
lecture notes from MIT/Harvard/etc. By the way, I did a Google search
and I came across a CACHED version of one lecture note from MIT -
<http://theory.lcs.mit.edu/~madhu/FT99/lect1.ps> page 4. Here, in the
second para under the heading "3.3 NP-Optimization Problems", it says
something. Unfortunately I do not have the .PS reader in my PC (and the
above file happens to be .PS), so I am unable to read the special
symbols (like = or <=) what they are saying.

Could u please help me find some strong references, which say whether
the "only =" version is also NP-Complete.

Hi,

Does it make any difference? We can transform every NP problem to HC
and then build TSP with question PATH==N, that means that every NP
problem can be transformed to version having == in question.

In mine opinion <= is used to show that we are asking for optimal tour
instead of tour of size N, but it does not matter for me.

Cheers,

Radek Hofman

.

Relevant Pages

  • Re: Discussion about transformation TSP to UniqueTSP
    ... reduction from a known NP-complete language such as Hamiltonian circuit. ... where the number of cities in TSP1 is equal ... TSP tour of length=N?". ...
    (comp.theory)
  • Re: Discussion about transformation TSP to UniqueTSP
    ... TSP is the question of whether the *optimal* tour has length = C. ... NP-complete, but I don't see immediately how to prove that. ... all the edges cost one, then add all possible edges assigning cost ...
    (comp.theory)
  • Re: Discussion about transformation TSP to UniqueTSP
    ... deepakc wrote: ... This problem is usually called the EXACT TSP problem. ... TSP is the question of whether the *optimal* tour has length = C. ... NP-complete, but I don't see immediately how to prove that. ...
    (comp.theory)
  • Re: Discussion about transformation TSP to UniqueTSP
    ... We can transform every NP problem to HC ... instead of tour of size N, but it does not matter for me. ... is greater then sum of weights then in fact we deal with different TSP ... to HCP and then get a Question of whether there is tour of length = N". ...
    (comp.theory)
  • Re: Discussion regarding Mr. Diabys algorithm
    ... TSP instance have a tour of cost <= C?"? ... I don't think it is possible to transform a TSP with multiple optima to ...
    (comp.theory)