# Complexity of calculating the optimal amalgamation of an optimal cycle-cover

Let $$G(V,E)$$ be a complete symmetric graph with positive edge weights and let further $$\mathcal{C}=\lbrace C_1,\,\cdots\,C_k\rbrace$$ be the minimum-weight vertex-disjoint cycle cover.
The set $$E$$ of edges is then the disjoint union of three kinds of edges: $$E=\lbrace C,\,D,\,X\rbrace$$, where

• $$C$$ are the edges of the vertex-disjoint cycle cover,
• $$D$$ are the diagonals of cycles, i.e. edges whose adjacent vertices belong to the same cycle in the cover, but are not adjacent to same cycle-edge and
• $$X$$ are the edges whose adjacent vertices belong to different cycles of the cover.

Question:

what is known about the complexity of determining the sets $$\lbrace c_{ij}\in C$$ of $$k\le r\le 2(k-1)$$ cycle-edges that,when optimally replaced by a set $$x_{ij}\in X$$ cross-edges yields the shortest tour that can be generated from the cycle-cover by exchanging not more than $$2(k-1)$$ cycle-edges with elements from $$X$$? The image illustrates two extreme cases of cycle amalgamation into a tour: on the left the original circles (depicted in gray) are in a tree-like configuration and thus require replacing $$2(k-1)$$ cycle-edges, whereas on the right they are in a more cyclic configuration and require only exchanging of $$k$$ cycle-edges to generate the "optimal" tour.

I just realized that there is a trivial reduction to the TSP problem by deleting all diagonals of every cycle, i.e. all edges of set $$D$$ in the question.