Asymptotically optimal approach to the approximate solution of several problems of covering a graph by nonadjacent cycles

We consider the $m$-Cycle Cover Problem, which consists in covering a complete undirected graph by $m$ vertex-nonadjacent cycles with extremal total edge weight. The so-called TSP approach to the construction of an approximate algorithm for this problem with the use of a solution of the traveling salesman problem (TSP) is presented. Modifications of the algorithm for the problems Euclidean Max $m$-Cycle Cover with deterministic instances (edge weights) in a multidimensional Euclidean space and Random Min $m$-Cycle Cover with random instances $UNI(0,1)$ are analyzed. It is shown that both algorithms have time complexity $\mathcal{O}(n^3)$ and are asymptotically optimal for the number of covering cycles $m=o(n)$ and $ m\le \frac{n^{1/3}}{\ln n}$, respectively.