Bottleneck TSP with repeated nodes

Question

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.

Answer 1

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