## 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. A special case of L-cycle covers are k-cycle covers for k ∈ ℕ, where the length of each cycle must be at least k. 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 with factor 2.5 for undirected graphs and with factor 3 in the case of directed graphs. Finally, we show that 4-cycle covers of maximum weight in graphs with edge weights zero and one can be computed in polynomial time. As a by-product, we show that the problem of computing minimum vertex covers in λ-regular graphs is APX-complete for every λ ≥ 3.

Original language | English |
---|---|

Title of host publication | Approximation and Online Algorithms |

Subtitle of host publication | Third International Workshop, WAOA 2005, Palma de Mallorca, Spain, October 6-7, 2005, Revised Papers |

Editors | Thomas Erlebach, Giuseppe Persinao |

Place of Publication | Berlin, Heidelberg |

Publisher | Springer |

Pages | 282-295 |

Number of pages | 14 |

ISBN (Electronic) | 978-3-540-32208-5 |

ISBN (Print) | 978-3-540-32207-8 |

DOIs | |

Publication status | Published - 10 Jul 2006 |

Externally published | Yes |

Event | 3rd International Workshop on Approximation and Online Algorithms, WAOA 2005 - Hotel Tryp Bellver, Palma de Mallorca, Spain Duration: 6 Oct 2005 → 7 Oct 2005 Conference number: 3 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer |

Volume | 3879 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Workshop

Workshop | 3rd International Workshop on Approximation and Online Algorithms, WAOA 2005 |
---|---|

Abbreviated title | WAOA |

Country/Territory | Spain |

City | Palma de Mallorca |

Period | 6/10/05 → 7/10/05 |