Approximability of Minimum-weight Cycle Covers
Bodo Manthey · arXiv (Cornell University) · 2006
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 ⊆ N. For most sets L, computing L-cycle covers of minimum weight is NP-hard and APX-hard. While computing L-cycle covers of maximum weight admits constant factor approximation algorithms (both for undirected and directed graphs), almost nothing is known so far about the approximability of computing L-cycle cover of minimum weight. We investigate how well L-cycle covers of minimum weight can be approximated. For undirected graphs, we give a positive answer: We devise a polynomial-time algorithm for approximating the L-cycle cover problem in undirected graphs. Our algorithm achieves an approximation ratio of 4 and works for all sets L. For directed graphs, we give a negative answer by proving an unconditional inapproximability results: If the set L is immune, then the problem of computing L-cycle covers of minimum weight in directed graphs cannot be approximated within a factor of o(n) where n is the number of vertices. Finally, we present an improved approximation algorithm for computing L-cycle covers of maximum weight in directed graphs. This algorithm achieves an approximation ratio of 8/3.