Cycle Covers: Algorithms and Approximability

A cycle cover of a graph is a set of cycles such that every
vertex is part of exactly one cycle. Cycle covers play an
important role in the design of approximation algorithms for
combinatorial optimization problems such as the traveling
salesman problem. To improve the approximation ratios
achieved by cycle cover based algorithms, it is helpful to
rule out certain cycle lengths a priori. Therefore, we
consider restricted cycle covers: An L-cycle cover is a
cycle cover in which the cycle lengths are restricted to be
in the set L.

We survey algorithms for and (in-)approximability of the
L-cycle cover problem. On the one hand, we show that the
problem is hard to approximate for almost all sets L. On the
other hand, we devise approximation algorithm for several
variants that work for arbitrary sets L.