Traveling salesman problem on an incomplete graph

Question

In the standard framing of the traveling salesman problem, we're given a complete graph, meaning every pair of vertices has an edge in between them. And this might be close to accurate when the salesman is flying between cities. If he's driving however, road networks tend not to be dense. You can drive from any city to any other city, but often you'll be hitting other cities on the way.

As an example, the picture below shows the graph of the road network for Ukraine. If you drive from Chernihiv (way North) to Odesa (way South), you will hit Kyiv and other cities on the way.

So, what if a salesman wants a driving tour that visits all cities in Ukraine? One thought is to construct the transitive closure of the road network graph and then apply standard traveling salesman algorithms to it.

But, this will include tours that are obviously sub-optimal because they'll (for example) go from Chernihiv to Odesa and then back to Kyiv, instead of simply stopping at Kyiv on the way.

Is there a way to take the structure of the graph into account while devising a tour that covers all cities? Of course, we can't guarantee that a Hamiltonian tour exists and we could be forced to visit some cities multiple times.

Answer 1

Let $G$ be your original graph and let $G'$ be its transitive closure.

Let $C'$ be an optimal tour in $G'$, and let $C$ be the tour in which you replace each edge $(u,v)$ of $C'$ with a shortest path between $u$ and $v$ in $G$. The tour $C$ is optimal in $G$ (even if it visits a city more than once).

To see this, let $w(C')$ (resp. $w(C)$) denote the cost of $C'$ (resp. $C'$). Let $w^*$ be the cost of an optimal tour of $G$. Clearly $w(C) \ge w^*$. Since all tour in $G$ are also tours in $G'$, we have $w(C') \le w^*$. Finally the cost of $C$ is at most the cost of $C'$ by construction. Therefore: $$ w^* \le w(C) = w(C') \le w^*. $$