# Bottleneck TSP with repeated nodes

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.

• 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? Commented Oct 7, 2020 at 8:23

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