Reduction from TSP to ATSP does not imply constant factor approximation algorithm As I understand there is a constant factor approximation algorithm (e.g Christofides algorithm) for the symmetric TSP problem. This is however not the case for the asymmetric TSP problem (I am assuming we are talking about the metric case for both).
According to Wikipedia there is a reduction from ATSP to TSP, which then can be solved to obtain a solution for the ATSP instance - so why does a solution on this reduction not imply that there is a constant factor approximation for ATSP?
I think the reduction they showed is incorrect. Where it falls is when you connect a node to its &quot;ghost&quot; with 0 cost and add a positive $w$ to all other edges. We will take a look why such a behavior can change the optimal path.
Indeed, take a look at a graph with nodes $v_0,\dots,v_{10}$ where we want to find the shortest path between $v_0$ and $v_{10}$.
The graph's edges will connect $v_i$ to $v_{i+1}$ with weight $1$, and will additionally connect $v_0$ to $v_{10}$ with weight $15$.
Clearly, the path between $v_0$ to $v_1$ and so on until $v_{10}$ has the lowest cost, of $10$.
But now assume we added to all edges a weight $w=1$. Then, this path's value will double to $20$, and the edge between $v_1$ and $v_{10}$ will have weight $16$.
Obviously, the shortest path now is the direct path $v_0,v_{10}$ with cost $16$, hence the optimal path changed.
Important note: Its possible to find a small enough $w$ that will not change the optimal path, but I believe finding one is NP-hard.