Let $G$ be a complete graph with weights. $MST(G)$ is the length of it's minimal spanning tree and $TSP(G)$ is the length of minimal travelling salesman path (length I suppose it's the sum of weights on the path/tree). The minimal travelling salesman is not the standard one, because the salesman can visit cities multiple times (though he has to end up in the same one), therefore it's not a hamilton cycle, and can be though of as a path on the spanning tree. I have to prove, that the following inequalities hold.

$$MST(G) \leq TSP(G) \leq 2MST(G)$$

I think that I know how to prove $MST(G) \leq TSP(G) $. If we take a minimal travelling salesman path then it's obviously a connected graph, and therefore we can create a spanning tree out of it (if it's not already one). This tree has to have the sum of weights $\geq$ then $MST(G)$, then the original graph also fullfils this inequality.

But what about $TSP(G) \leq 2MST(G)$? I would try constructing the travelling salesman path from the $MST$ to prove it. Let's take that $MST$ from the designated city. Let's DFS it from this city. A DFS path contructed this way designates our traveling salesman route (everytime we enter a child we count the edge, everytime we backtrack in our algorithm we count it again), each edge is counted twice, so our travelling salesman path is of length $2MST(G)$.

Is this correct in any way?

  • 1
    $\begingroup$ I believe you have found the standard argument for the upper bound on the travelling salesman path. $\endgroup$ – Gerry Myerson Jan 13 '14 at 19:02
  • $\begingroup$ So both arguments are correct? Or am I missing some detail? $\endgroup$ – Arek Krawczyk Jan 13 '14 at 19:03
  • 1
    $\begingroup$ There's always room for more detail --- the appropriate amount depends on the circumstances --- but I'd accept both arguments. $\endgroup$ – Gerry Myerson Jan 13 '14 at 22:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.