Return to Revisions

Meanwhile I found the solution:

1. split every vertex into $k+1$ copies
2. set the distance between vertex-copies to $0$
3. Construct the $k$-factor gadgets of Tutte, resp. of Lovasz and Plummer, by again splitting the vertex-copies from step. 1 into as many copies as required for calculating the $k$-factor of the graph generated in step 1. and finally adding the edges required for the $k$-factor gadget.
4. calculate the maximum weight perfect matching of the graph of step 3.
5. delete from the matching all edges of the $k$-factor gadget and all edges between vertex copies of step 1.

In the case of complete graphs we ge: after step 1. $n$ vertices of degree $(n-1)+k$ and $\frac{(n+-1+k)\cdot n}{2}$ edges. constructing the gadgets for a $k$-factor splits a vertex of degree $d$ into at least $d+2$ copies and adds at least $2\cdot d$ edges per gadget. We have $d=n-1+k$ and thus $(n-1+k+2)\cdot n$ vertices and $\frac{n\cdot(n-1+k)}{2}+n\cdot (n-1+k)$ edges in the graph where the maximum weight perfect matching is determined from which the maximum weight matching of the original graph can be determined.