Graph Processing: travel to each node at least once, start and end at specific (same) node?

Question

I've found myself where I've got a bidirectional graph of roughly 5500 nodes, 14000 edges.

I'd like to visit ~85 of these nodes, each at least once, starting and ending at the same node. I'd like to get a short route (don't need explicitly shortest, though that would be nice!). What graph processing algorithm should I use in this situation?

I feel like this isn't that unusual of a problem, but I think I'm searching for the wrong terms, as searching around has turned up fruitless. Or maybe I just haven't practiced math in too long!

The cost for traveling between two connected nodes is all the same.

Answer 1

Create a graph with only the nodes of interest, and calculate for each pair the shortest distance (there are polynomial procedures for calculating the transitive closure of a graph).

Now you're looking for a relaxed version of the Traveling Salesman Problem.

Therefore, in this modified version, you can at least find an approximation algorithm using the MST of the modified graph with a factor of 2x (i.e. it is, at worst, twice as bad as the optimal route).

I'm not 100% sure, but I think the relaxed version of TSP was NP-complete as well, so searching for anything better than an approximation algorithm would be out of reach.

Either way, with this modification done, you can use everything we know about the TSP and apply it onto it.

Answer 2

What you could do for instance is the following:

For every one of your $85$ nodes use a shortest path algorithm (like Dijkstra) to find shortest paths to all other $84$ nodes. Use this information to build a new complete graph with $85$ nodes. Now if the costs of your initial graph satisfy the triangle equality, then it will also be satisfied in the new graph. Hence you can use an approximation algorithm for the metric travelling salesman problem to find a good route in your new graph.

Note that every edge in the new complete graph corresponds to a path in the old graph and thus when you found a route in the new graph you can just substitute every edge on that route with the corresponding path in the old graph.

Note also that the following can happen: When looking for a shortest path from $v$ to $w$ in the old graph where $v, w$ are of the distinguished $85$ nodes, then it is possible that some other node $u$ of the distinguished nodes is on that shortest path. Hence your result might include several visits of one of the distinguished nodes.