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.


1 Answer 1


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.

  • $\begingroup$ A bit of nitpicking (sorry): If TSP is not metric, then the problem becomes probably harder. $\endgroup$
    – A.Schulz
    Jul 4, 2013 at 7:16
  • $\begingroup$ @YuvalFilmus So, in my case, I cannot give weights to the non-edges such that the complete graph still satisfies the triangle inequality (infinite weight will violate this property)? $\endgroup$ Jul 4, 2013 at 11:46
  • $\begingroup$ You might be able to choose weights that would make the graph satisfy the triangle inequality, but then a TSP tour could contain these edges. $\endgroup$ Jul 4, 2013 at 14:17
  • $\begingroup$ @YuvalFilmus Can you shortly explain how to do that? (a TSP tour may contain one or more new edges.) Thank you. $\endgroup$ Jul 4, 2013 at 17:02
  • 1
    $\begingroup$ If you start with a graph which doesn't falsify the triangle inequality, I think that you can give each missing edge the weight of the shortest path linking the two vertices, and then the result satisfies the triangle inequality. But I might be wrong on that. $\endgroup$ Jul 4, 2013 at 17:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.