Minimum-weight Cycle Covers and Their Approximability
<|reference_start|>Minimum-weight Cycle Covers and Their Approximability: 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.   We investigate how well L-cycle covers of minimum weight can be approximated. For undirected graphs, we devise a polynomial-time approximation algorithm that achieves a constant approximation ratio for all sets L. On the other hand, we prove that the problem cannot be approximated within a factor of 2-eps for certain sets L.   For directed graphs, we present a polynomial-time approximation algorithm that achieves an approximation ratio of O(n), where $n$ is the number of vertices. This is asymptotically optimal: We show that the problem cannot be approximated within a factor of o(n).   To contrast the results for cycle covers of minimum weight, we show that the problem of computing L-cycle covers of maximum weight can, at least in principle, be approximated arbitrarily well.<|reference_end|>
@article{manthey2006minimum-weight,
    title={Minimum-weight Cycle Covers and Their Approximability},
    author={Bodo Manthey},
    journal={arXiv preprint arXiv:cs/0609103},
    year={2006},
    archivePrefix={arXiv},
    eprint={cs/0609103},
    primaryClass={cs.DS cs.CC cs.DM}
}