# Traveling salesman problem on an incomplete graph

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.

• Do you need to visit each city exactly once? Commented Nov 6, 2022 at 19:57
• No. That might be impossible in general. Commented Nov 6, 2022 at 20:07
• If you don't need the graph to be metric then you can just set the weight of the missing edges to $+\infty$. Commented Nov 6, 2022 at 20:13
• What is a metric graph? Commented Nov 6, 2022 at 20:26
• A graph in which edge weights satisfy the triangle inequality. For any triple of vertices $u,v,x$, $w(u,v) \le w(u,x) + w(x,v)$, where $w(a,b)$ denotes the weight of the (generic) edge $(a,b)$. Commented Nov 6, 2022 at 20:59

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^*.$$
• $w(C')$ (resp. $w(C)$) what does this statement mean? Commented Nov 6, 2022 at 20:25
• resp. stands for respectively. It's just a compact way to define two quantities at once. I'm defining $w(C')$ as the cost of $C'$ and $w(C)$ as the cost of $C$. Commented Nov 6, 2022 at 20:54