Approximation Algorithms for Restricted Cycle Covers Based on Cycle Decompositions
<|reference_start|>Approximation Algorithms for Restricted Cycle Covers Based on Cycle Decompositions: A cycle cover of a graph is a set of cycles such that every vertex is part of exactly one cycle. An L-cycle cover is a cycle cover in which the length of every cycle is in the set L. The weight of a cycle cover of an edge-weighted graph is the sum of the weights of its edges.   We come close to settling the complexity and approximability of computing L-cycle covers. On the one hand, we show that for almost all L, computing L-cycle covers of maximum weight in directed and undirected graphs is APX-hard and NP-hard. Most of our hardness results hold even if the edge weights are restricted to zero and one.   On the other hand, we show that the problem of computing L-cycle covers of maximum weight can be approximated within a factor of 2 for undirected graphs and within a factor of 8/3 in the case of directed graphs. This holds for arbitrary sets L.<|reference_end|>
@article{manthey2006approximation,
    title={Approximation Algorithms for Restricted Cycle Covers Based on Cycle
  Decompositions},
    author={Bodo Manthey},
    journal={arXiv preprint arXiv:cs/0604020},
    year={2006},
    archivePrefix={arXiv},
    eprint={cs/0604020},
    primaryClass={cs.DS cs.CC cs.DM}
}