Approximation algorithm for TSP variant, fixed start and end anywhere but starting point + multiple visits at each vertex ALLOWED

NOTE: Due to the fact that the trip does not end at the same place it started and also the fact that every point can be visited more than once as long as I still visit all of them, this is not really a TSP variant, but I put it due to lack of a better definition of the problem.

This problem was originally posted on StackOverflow, but I was told that this would be a better place. I got one pointer, which converted the problem from non-metric to a metric one.

So..

Suppose I am going on a hiking trip with n points of interest. These points are all connected by hiking trails. I have a map showing all trails with their distances, giving me a directed graph.

My problem is how to approximate a tour that starts at a point A and visits all n points of interest, while ending the tour anywhere but the point where I started and I want the tour to be as short as possible.

Due to the nature of hiking, I figured this would sadly not be a symmetric problem (or can I convert my asymmetric graph to a symmetric one?), since going from high to low altitude is obviously easier than the other way around.

Since there are no restrictions regarding how many times I visit each point, as long as I visit all of them, it does not matter if the shortest path from a to d goes through b and c. Is this enough to say that triangle inequality holds and thus I have a metric problem?

I believe my problem is easier than TSP, so those algorithms do not fit this problem. I thought about using a minimum spanning tree, but I have a hard time applying it to this problem, which under the circumstances, should be a metric asymmetric directed graph?

What I really want are some pointers as to how I can come up with an approximation algorithm that will find a near optimal tour through all n points

• Is your graph planar? (Or are you hiking in a network of caves?) – JeffE Apr 28 '12 at 14:39
• It is safe to assume that the graph is planar, yes – Casper Apr 29 '12 at 10:29
• That makes the problem much easier; see courses.csail.mit.edu/6.889/fall11/lectures/L15.html – JeffE Apr 29 '12 at 16:07
• @JeffE, As you said seems this problem is equivalence with TSP (with a little variation), but why? I prove it partially (I should cover more general possibilities), but my proof is not simple and obvious, but seems it's obvious for you, I think I missed something which eases this conversion, would you please tell me why this is obvious for you? – user742 Apr 29 '12 at 20:55
• For each pair of vertices $(u,v)$, redefine the weight of edge $uv$ to be the shortest path distance from $u$ to $v$. Now three facts are easy to prove. (1) The optimal tours in the original graph and new graph have identical weight. (2) The optimal tour in the new graph never visits a vertex more than once. (3) Edge weights in the new graph obey the triangle inequality. So in the new graph, the problem is precisely metric traveling salesman. – JeffE Apr 30 '12 at 7:10

I don't know how to solve your problem or show its NP-Hardness but you can find all pair shortest path to convert your graph to metric one, just replace $e_{a,b}$ with shortest path from a→b and if there isn't edge between $a,b$ add new edge with shortest path weight, now you can run some approximation for TSP to find approximation for your problem, as I know best approximation for TSP is currently $O({\log n \over \log{ \log n}})$. Base idea is using Held-Karp relaxation and finding special spanning tree then using method like Christofides algorithm. (it has some new definitions like Thin tree, ... which makes it harder than other methods for asymmetric case), you can also use known $O(\log n)$ approximations. Also I thought about your problem to approximate it with a minimum cycle cover, but I couldn't get good result. If I found anything I'll update this answer.
• @Casper, No MST is not good for you, except your problem is on undirected graphs, in that case there is 3/2 approximation, see christofides algorithm. In the paper I offered you they using flow to find a good tree (named it Thin tree), the main attribute of this tree is it's very thin :) means maximum min-cut over all possible spanning trees in the graph is minimized, I think this can get some intuition why for asymmetric case this tree is useful. However I have a strong feeling which says your problem belongs to $P$ :) – user742 Apr 29 '12 at 10:41