# Asymmetric metric TSP when many edges have equal costs in both directions

I would like to ask whether there exists a better approximation result on a special case of the ATSP metric instances: when cost(a,b)=cost(b,a) for $O(log(|E|)$ edges, or something close/related to that (in fact when this holds for the 'small-cost' edges). Thank you

• I think this needs to be worded more carefully. What's stopping you from taking a standard ATSP instance and replacing a vertex with a clique of size $O(\sqrt{\log n})$ with all inner-distances $\epsilon$? – Yonatan N Jan 22 '14 at 9:12
• It should be worded better. Assume that there exist $|V|/2$ distinct pairs of vertices with symmetric 'small costs' (i.e. these are the $|V|/2$ smaller edge costs of the graph). I did not want initially to be more specific, thats why I asked for a close/related result. Thanks – NicosM Jan 22 '14 at 9:26
• You still end up with the same problem in that case, as can be seen by replacing every vertex with a length-2 path with distance $\epsilon$. I can't imagine the problem becomes much easier without having something like $(1-o(1))|E|$ symmetrical edges, as replacing each vertex of the graph with a sufficiently large $\epsilon$-distance clique pads the count of small, symmetrical edges without changing the problem significantly (for small enough $\epsilon$). – Yonatan N Jan 22 '14 at 22:00
• Yes, you are right. We need something like (1-o(1))|E|. Thanks – NicosM Feb 11 '14 at 9:21