What is the graphic TSP?

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?

• To me it sounds like a solution for G' may contain edges that do not exist in G – Auberon Jun 14 at 14:00
• Sounds right. ~~~ – Yuval Filmus Jun 14 at 14:05

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.

• I like the "for reasons nobody can really explain" – J. Schmidt Jun 15 at 14:59

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.

• If $G$ is not connected then there are no tours. – Yuval Filmus Jun 14 at 14:53
• @yuval Yes. That doesn’t (necessarily) mean that GTSP is undefined as a problem for disconnected graphs though. – Stella Biderman Jun 14 at 16:24
• 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'. – J. Schmidt Jun 16 at 8:19