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{(nk-1)\cdot nk}{2}$ edges. constructing the gadgets for a $k$-factor splits a vertex of degree $d$ into at least $d+k$ copies and adds at least $k\cdot d$ edges per gadget. We have $d=n-1+k$ and thus $(n-1+k+k)\cdot n$ vertices and $\frac{(nk-1)\cdot nk}{2}+(n-1+k)nk$ 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.