0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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