2
$\begingroup$

Are there any advantages in finding the shortest tour for the problem if edge weights are much smaller than the number of vertices?

Let's say the maximum edge weight is $n$, and the number of vertices is $n!$, and the adjacency matrix is dense and all distances $d_{ij}$ satisfy $0 \le d_{ij} \le n$. Are there any known methods which work well in similar cases?

Improve this question
$\endgroup$
2
  • $\begingroup$ In the classical definition of TSP, the graph is complete, so the adjacency matrix is always dense. $\endgroup$
    – David Richerby
    Apr 9, 2018 at 11:10
  • $\begingroup$ Yes, but I wanted to explicitly point out that I'm not interested in sparse instances if sparseness simplifies things. For example, science.sciencemag.org/content/251/4995/754, these guys solve to optimality instances with hundreds of thousands of nodes by exploiting the fact that their graph is not complete (or at least they make it incomplete by removing edges above some weight threshold). I was wondering if there are similar exploits for my case. My matrices are just like the definition above and most of the edges have the maximum edge weight $n$ (more than 80% of the edges). $\endgroup$
    – Looft
    Apr 9, 2018 at 11:21

1 Answer 1

Reset to default
3
$\begingroup$

Travelling salesman remains NP-complete even if you restrict to two different edge weights $a<b$. Reduce from Hamiltonian cycle by giving weight $a$ to every edge and weight $b$ to every non-edge. Then the resulting complete graph has a TSP tour of length $na$ (where $n$ is the number of vertices) if, and only if, the original graph has a 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.