1
$\begingroup$

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$?

Illustration of amalgamation of cycle covers

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.

$\endgroup$
0
$\begingroup$

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.

The optimal tour in the thus modified graph is also the result of optimally merging the cycles of the cover.

The question remains however what the opposite direction, namely reducing the TSP to minimum-weight vertex-disjoint cycle means complexity-wise for the cycle-amalgamation problem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.