Hacker News Reader

First, use binary search to find answer. Then, remove edges one-by-one if removing this edge will not destroy all remaining path with shortest length, until your graph is reduced to a single cycle.

View on HN

Thanks for the answer, I have edited my post and I have basically the same solution. (Only instead of removing the edges I increase their weight to infinity because I think the TSP problem is defined only on complete graphs) But as I have mentioned in my comment I feel like this solution is flawed.

You can without loss of generality assume that the weights are integers (if they are rational, you can multiply all weights so that they become integral).

Hence, you can use bisection to compute the actual optimum, not involving epsilon at all.

Reply on news.ycombinator.com