Skip to main content
MathOverflow

Return to Answer

improved the calculation of the number of vertices and edges
Source Link
Manfred Weis
Manfred Weis
  • 13.2k
  • 4
  • 34
  • 76

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

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.

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.

Source Link
Manfred Weis
Manfred Weis
  • 13.2k
  • 4
  • 34
  • 76

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.