0
$\begingroup$

I am aware that the traveling salesman problem (TSP) and the bottleneck TSP problem is NP-hard for complete directed graphs. I am also aware that regular TSP that allows a path with repeating is also NP-hard. However, I was not able to find a reference for the complexity of the bottleneck TSP problem with repeated nodes for complete graphs.

Also, I am curious if continuously removing the most costly edges until all nodes are not strongly connected actually solves this problem. I think that this method should solve this problem, but I was not sure about it.

$\endgroup$
1
  • $\begingroup$ Welcome to COMPUTER SCIENCE @SE. I see multiple questions here: put in separate posts 1) What are commendable reference texts for the complexity of the bottleneck TSP problem with repeated nodes for complete graphs? 2) Does [this algorithm] actually solve this problem? $\endgroup$
    – greybeard
    Oct 7 '20 at 8:23
0
$\begingroup$

The problem is in P.

You can solve the decision problem in $O(n^2)$ time, where $n$ is the number of vertices (i.e., linear time in the size of the input). Delete all edge whose weight is above the bottleneck threshold. Form the strongly connected components of the resulting graph, and examine its metagraph. The original decision problem has a bottleneck TSP iff the metagraph is a simple path, i.e., it has the form $w_1 \to w_2 \to \dots \to w_k$ where $w_1,\dots,w_k$ are the components and the only edges are $w_i \to w_{i+1}$.

You can solve the optimization problem in $O(n^2 \log n)$ time. Sort the set of edge weights, and remove duplicates. Then, use binary search on this set of weights to find the smallest bottleneck threshold such that the decision problem has a solution. You will do $O(\lg n)$ iterations, and each iteration runs the decision problem above, so the total running time is $O(n^2 \lg n)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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