Removing one edge at a time won't work if there is a second, redundant, optimal path (every edge can be removed without altering the cost). I don't remember how you get around this but it shouldnt be too complicated...
Re:The TSP Isn't NP Complete
by ColinWright on Tuesday December 31, 2013 @03:42AM
(#6989656)
Sorry, thought that was clear. If you remove an edge and find the cost doesn't change, don't put the edge back - carry on with the smaller graph.
It's not a path that we're feeding to the decision problem. The decision problem is when we have a graph with costs on the edges, and when someone says "Is there a solution of cost less than K?" We're assuming we have a way to answer that, and using that to get a solution to the optimization problem.
We need to use that to find the best possible path. We start by finding the cost of the best possible path. Set k=1 and ask if there's a solution. If not, double K and ask again. Repeat until the answer is "Yes".
Now you know there is a solution with cost in the range [0,K]. Set L=0 and U=K. Now do a binary search. Set K = L + (U-L)/2 and ask if there is a solution of cost K. If not, set L=K, if so then set U=K. Lather, rinse, repeat, until U-L is sufficiently small (1 if using integer weights - more care required otherwise).
Now we know the optimum price. Remove an edge and see if there's still a solution. If there is, there's an optimal path without it. If not, the edge is in the optimal path. Repeat for all edges - some efficiencies can be made.