# Solving a modified Travelling Salesman Problem(TSP)

I am trying to solve a modified version of the TSP. In my version, multiple visits to a city are allowed, as long as the path is the shortest, and also, only subset of the cities are compulsory to visit, as in, you can go through other cities to visit all the subset cities if path is shorter, but if not, the other cities can be ignored. For simplicity, starting city is fixed. Also, all cities are not connected to others directly. I know approx. solutions for the traditional TSP, but, I have trouble solving this one. A naive approach can be to find all possible combinations of the subset cities and check which has the shortest total path length, but that solution will have a n^2 complexity for trying each combination, plus the complexity for finding shortest path for each two cities. So, what should I use to solve this problem?

• You can just restrict to the "interesting'" cities by computing shortest paths between them. Allowing multiple visits just lengthens the tour, at least if the triangle inquality is satisfied. Mar 1 '20 at 19:28
• @vonbrand but there can be case that the path across another city is shorter than the direct path Mar 1 '20 at 23:46

As mentioned in the comments, you can compute APSP (All-Pairs Shortest Paths) at first and build the matrix $$D:=\left(d_{ij}\right)_{i,j\in[n]}$$, where $$d_{ij}$$ is the length of a shortest path from the vertex $$i$$ to the vertex $$j$$. By solving the usual travelling sales man on the graph $$G'$$ where $$D$$ is the adjacency matrix, you get a solution for your version of the problem. Try to see why this works as an exercise.
Note that $$D$$ defines a metric and metric TSP admits a polynomial time 1.5-approximation. The same Wikipedia article contains more information about this algorithm under the section "Constructive heuristics".
• APSP is all pairs shortest paths. In short for each pair of vertices $u$ and $v$ set the length of the edge $\{u, v\}$ to be $d_{u,v}$, the length of the shortest path from $u$ to $v$. Solving TSP on the resulting graph would solve your special version of the problem on the input graph. Mar 1 '20 at 23:59