0
$\begingroup$

Calculating lightest vertex-disjoint cycle covers of finite complete symmetric graphs with weighted edges can be done efficiently and also renders the edge set of the calculated cycles free of pairs of crossing edges.

Calculating the unconstrained heaviest cycle cover will however generate edge sets with many pairs of crossing edges, leading to the

Question:
what is the complexity of calculating heaviest 2-optimal vertex-disjoint cycle covers, i.e. if constraints are added that make crossing edges mutually exclusive?

The motivation for the question is the observation that the minimal cycle cover may contain cycles that are far apart, thus making it hard to merge these cycle in an optimally to get an approximation of the shortest Hamilton cycle.
For heaviest 2-optimal cycle covers we may expect many pairs of long edges for which the minimum-weight matching of the $K_4$ that is induced by their adjacent vertices is small, thus easing the task of optimally merging the cycles to a short tour.

Improve this question
$\endgroup$
2
  • $\begingroup$ Are you assuming the weights satisfy the triangle inequality? $\endgroup$
    – RobPratt
    Commented Jan 29, 2021 at 4:56
  • $\begingroup$ @RobPratt yes, otherwise a sufficienctly large constant may be added to edge's weight to make the instance obey the triangle inequatity $\endgroup$
    – Manfred Weis
    Commented Jan 29, 2021 at 5:03

0

Reset to default

You must log in to answer this question.