1
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Discrete lizard ♦
    Feb 2, 2018 at 14:54

1 Answer 1

Reset to default
3
$\begingroup$

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$ 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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.