__
TR07-011 | 19th December 2006 00:00
__

#### On Approximating Restricted Cycle Covers

**Abstract:**
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.