I'm not sure if I understand the following definition of the (well-known apparently) Graphic TSP, also known as graph-TSP :
...graph-TSP, that is, the traveling salesman problem where distances between cities are given by any graphic metric, i. e., the distance between two cities is the length of the shortest path in a given (unweighted) graph.
this is from Mömke and Svensson's paper : https://arxiv.org/pdf/1104.3090.pdf
I understand this as follows :
- one is given an input graph, say G, that is unweighted (and supposedly connected).
- one then can construct a complete graph, say G', where cost of edge (u,v) is the minimum distance between u and v in G.
- obtaining an optimal TSP solution in G' results in an optimal solution for the graphic TSP on G.
Is this correct?