Dear list, In the boost/graph/metric_tsp_approx.hpp:224 is a note // TODO: This is will be O(n^2) if vertex storage of g != vecS. Since I am exactly in this situation I made a patch for my use, I added a bundled property to MSTImpl's vertices to contain a descriptor to keep track of the original graph vertices. It is a small modification, but since there is a TODO perhaps there is interest? If so how should I share it? Of course any comment is welcome. Your sincerely, Paolo