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.
You're just trying to find Hamiltonian cycles in unweighted graphs. That's still NP-complete.

If you want to do it with a TSP solver, do it as follows. Suppose you have a graph on $n$&nbsp;vertices. These are your $n$&nbsp;cities. If there's an edge between two vertices, set the distance between the corresponding cities to&nbsp;$1$. If there's no edge, set the distance to&nbsp;$2$. If a minimum-weight TSP solution has total weight&nbsp;$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.