Practical calculation of minimum weight vertex-disjoint cycle covers

Question

How are minimum-weight vertex-disjoint cycle covers of large dense symmetric graphs actually calculated in actual implementations?

I know that the problem can be reduced to general matching by utilizing either Tutte's gadget or the gadget suggested by Lovasz and Plummer; there is however a fly in the ointment with those reductions namely that each vertex of the original graph is replicated $O(n)$ times, yielding a matching problem for a graph with $O(n^2)$ vertices and thus an $O(n^6)$ algorithmic solution.

Question:

are the mentioned gadgets actually utilized for calculating lightest d-factors and especially 2-factors or, does the straight forward Linear Programming formulation provide significantly better performance resp. footprint and if so, which variant of Linear Programming is most appropriate, primal, dual, primal-dual, etc.

I need an efficient way of generating those cylce covers for investigating the performance of a new idea for a TSP heuristic.

Answer 1

A very simple and efficient heuristic that I found recently is as follows:

• proceed as in the calculation of Minimum Spanning Trees with Kruskal algorithm, i.e. by inserting edges into a Disjoint Set datastructure in order of increasing length.
• if adding an edge generates a cycle
  • add that cycle to the set of covering cycles
  • restart the algorithm with that cycle's vertices removed from the original graph provided at least 3 vertices are left.
• optimally integrate the remaining vertices into the reported cycles.

In case the original graph is bipartite, that algorithm can also be used as a heuristic for finding light matchings: every cycles has even length and thus is the union of two edge-disjoint matchings. The heuristic is then to take from every generated cycle the edges of the lighter matching; the step of integrating a leftover pair of vertices after the execution of cycle finding need not be performed for the matching heuristic.

The exact time complexity of the heuristic isn't known to me, but a coarse estimate is that every has length 3 and the MST algorithm is executed $\frac{n}{3}$ times, namely for graphs with $3k,\ k=\,1,\cdots,\,\frac{n}{3}$ vertices, i.e. $O(n^2)$.
That estimate ignores however the fact that the MSTs need not be completely constructed and only knowledge of bounds on the steps till the emerging of the first cycle and of the distribution of their sizes would allow for more realistic estimates.

please note that the above should be seen as a comment, but to give a visual clue to frequenters of MO that an idea is available and of course because of the length, I made it an answer.