Approximate perfect matching through MST

286 Views Asked by At

If I compute a minimum spanning tree T in a graph with an even number of vertices and T contains a perfect matching M (which is unique in this case), can I get some approximation guarantee on the weight of M in comparison to a minimum weight perfect matching M* in the graph, i.e. w(M) <= c * w(M*) for some c>=1?

Edit: Assuming non-negative edge-weights.

1

There are 1 best solutions below

0
On BEST ANSWER

Seems like the answer is no.

Consider the following graph: a cycle on vertices $A_1,A_2,\ldots,A_{2k}$, where the edge $A_1A_2$ has maximum weight $M$, any other edge of the form $A_{2l+1}A_{2l}$ has weight $1$, and all the edges of the form $A_{2l}A_{2l+1}$ have weight $M-1$, indices modulo $2k$.

Then the MST is obtained by removing $A_1A_2$, and it contains the unique matching consisting of all edges of the form $A_{2l}A_{2l+1}$, with total weight $k(M-1)$, whereas the minimum perfect matching on the graph is obtained from the edges of the form $A_{2l+1}A_{2l}$, with total weight $M + (k-1)$. Now as we increase $k$, the matching from the MST gets arbitrarily worse than the optimal one.