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.
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.