# Traveling salesman problem with disconnected cities / infinite length edge

I am looking to solve a variant of the traveling salesman problem with a certain set of constraints:

• the graph is not complete, i.e. some nodes are not connected to each other
• the weight of an edge between any pair of connected nodes is always 1

What is the best way to model and solve this problem?

AFAIK the Concorde TSP solver, for example, requires real numbers for edge weights. And it seems like because all the edges have the same weight, there could be more than one valid solution.

• This variant isn't much easier than TSP in general. At least, it is still NP-hard. You can reduce this version from Hamiltonian cycle similarly to this example: ida.liu.se/opendsa/OpenDSA/Books/Everything/html/… (replace 0 by 1 and 1 by infinity, and choose the appropriate length) . Still, there might be better ways to solve this specific case. – Discrete lizard Feb 2 '18 at 14:54

If you want to do it with a TSP solver, do it as follows. Suppose you have a graph on $n$ vertices. These are your $n$ cities. If there's an edge between two vertices, set the distance between the corresponding cities to $1$. If there's no edge, set the distance to $2$. If a minimum-weight TSP solution has total weight $n$, it's a Hamiltonian cycle of the original graph; if it has weight $n+1$ or more, then every cycle that visits all cities must include at least one non-edge of the graph, so the graph has no Hamiltonian cycle.