[Solved]: About metric TSP instances

Problem Detail: 

Christofides' 1.5-approximation considers complete graphs as inputs, and as I understand this is essential. If the input graph is not complete, how can I add new edges with suitable weights such that the resulting complete graph still satisfies the triangle inequality, and, of course, the TSP solution for the complete graph only uses original edges? Thank you.

Asked By : Jennifer Ng

Answered By : Yuval Filmus

If the edges don't satisfy the triangle inequality then the problem becomes harder. In your case the non-edges have infinite weight (since you want never to use them), so you can't expect Christofides' algorithm to be useful as such.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/13070