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

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.