1
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • $\begingroup$ To me it sounds like a solution for G' may contain edges that do not exist in G $\endgroup$ – Auberon Jun 14 at 14:00
  • $\begingroup$ Sounds right. ~~~ $\endgroup$ – Yuval Filmus Jun 14 at 14:05
2
$\begingroup$

Your understanding is correct.

The key point about TSP is that we are given a distance between every pair of cities. In other words, formally speaking, TSP is the problem of finding a minimum-weight Hamiltonian path/cycle on a weighted complete graph, given the weight function. This doesn't quite correspond to the standard intuition where a salesman is travelling around an actual road network and is forbidden from visiting the same city twice, for reasons nobody can really explain.

In graphic TSP, the distance function is defined in terms of some (possibly weighted, possibly directed) graph on the given vertices. This is much closer to the usual intuition about what TSP is: driving from, say, Baltimore to New York by the fastest route might involve passing through Philadelphia but, even if we've already visited Philadelphia, we're allowed to pass through again without stopping.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I like the "for reasons nobody can really explain" $\endgroup$ – J. Schmidt Jun 15 at 14:59
0
$\begingroup$

Yes, I agree with your characterization for connected graphs. In the case where $G$ is disconnected, you instead create a $G'$ which is the disjoint union of cliques, each corresponding to a different connected component of $G$. $G'$ will always contain edges not present in $G$, except in the case where $G$ is the disjoint union of cliques.

I generally think it's best to think of graph TSP as a data structure that augments the TSP that it is derived from.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ If $G$ is not connected then there are no tours. $\endgroup$ – Yuval Filmus Jun 14 at 14:53
  • $\begingroup$ @yuval Yes. That doesn’t (necessarily) mean that GTSP is undefined as a problem for disconnected graphs though. $\endgroup$ – Stella Biderman Jun 14 at 16:24
  • $\begingroup$ As I see it, if there are no tours (G not connected), then the problem becomes trivially unsolvable for Graphic TSP. Thus, there would be no need to create a G'. $\endgroup$ – J. Schmidt Jun 16 at 8:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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