Dear list, I am using boost graph and I need to solve a variant of the classic TSP. Boost providess a function (metric_tsp_approx) to get a Halmintonian cycle over a full connected metric weighted graph. However I need something slightly different. I need a path that visits all vertices starting and ending to two well known vertices (let be s and d). Seeking around, I found the suggestion of adding a node connected to s d and with the weight of the edge (s,d). The TSP solution of the new graph is the solution, just removing the new node. The problem is that now the graph is not complete anymore so the metric_tsp_approx's approach does not work anymore. Another possiblity is using a variant of Christofides algorithm, but one of the passages of that is the minimum weight perfect matching. I am a little confused by the documentation of the functions about Maximum Cardinality Matching(1), it is possible to use them to find the a maximum cardinality matching so that the total weight of all selected edges is minimal? Otherwise, is there an alternate approach to my problem? Yours faithfully, Paolo (1) http://www.boost.org/doc/libs/1_55_0/libs/graph/doc/maximum_matching.html