Re: Discussion about transformation TSP to UniqueTSP


Rados³aw Hofman wrote:
- decision version - each NP-complete problem can be transformed to Hamilton
Cycle problem which can be converted to TSP with question "Is there TSP tour
with overall Cost <=N" (in transformation we assign 1 to every arc existing
in HC instance and 100 for every arc added to obtain TSP instance) - this
makes decision version ask for optimal C, but after transformation we loose
this ability. My attempt to solve it via checking one by one N^2 problems is
incorrect - it will preserve correctness of solution, but it does not ensure
uniqueness of optimal assignment

I'm not entirely sold that this is true. You do know, trivially, that
N = N * multiplicitive cost + min(chose #_of_vertices - 1: of additive
costs). Where min satisfies 2^(1) + ... + 2^(number of vertices -1) <=
min <= 2^(number of edges) + ... + 2^((number of edges) - ((number of
vertices) -1)).

This reduces the options a lot, and I'd bet it still reduces quite a
bit further. For instance, you can limit the number of edges to 2 *
factorial(vertices) by reducing a general TSP so that only the cheapest
edge{a,b} is selected...

I think I read somewhere that a TSP with different costs for edge{a,b}
and edge{b,a} can be reduced to a (larger) TSP with edge{a,b} =
edge{b,a}. This limits the right side of the equality-relation in
min() to the factorial of the vertices.

A non-random distribution of additive costs might go a long way
further. ...anyway, I'm out of time right now.

.