## 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 ⊆ ℕ. For most sets L, the problem of computing L-cycle covers of maximum weight is NP-hard and APX-hard. We devise polynomial-time approximation algorithms for L-cycle covers. More precisely, we present a factor 2 approximation algorithm for computing L-cycle covers of maximum weight in undirected graphs and a factor 20/7 approximation algorithm for the same problem in directed graphs. Both algorithms work for arbitrary sets L. To do this, we develop a general decomposition technique for cycle covers. Finally, we show tight lower bounds for the approximation ratios achievable by algorithms based on such decomposition techniques.

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

Title of host publication | Graph-Theoretic Concepts in Computer Science |

Subtitle of host publication | 32nd International Workshop, WG 2006, Bergen, Norway, June 22-24, 2006 Revised Papers |

Editors | Fedor V. Fomin |

Place of Publication | Berlin, Heidelberg |

Publisher | Springer |

Pages | 336-347 |

Number of pages | 12 |

ISBN (Electronic) | 978-3-540-48382-3 |

ISBN (Print) | 978-3-540-48381-6 |

DOIs | |

Publication status | Published - 1 Jan 2006 |

Externally published | Yes |

Event | 32nd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2006 - Bergen, Norway Duration: 22 Jun 2006 → 24 Jun 2006 Conference number: 32 |

### Publication series

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

Publisher | Springer |

Volume | 4271 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Workshop

Workshop | 32nd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2006 |
---|---|

Abbreviated title | WG |

Country | Norway |

City | Bergen |

Period | 22/06/06 → 24/06/06 |