## 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 ⊆ ℕ. 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 - ε 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.

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

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

Subtitle of host publication | 33rd International Workshop, WG 2007, Revised Papers |

Publisher | Springer |

Pages | 178-189 |

Number of pages | 12 |

ISBN (Electronic) | 978-3-540-74839-7 |

ISBN (Print) | 978-3-540-74838-0 |

DOIs | |

Publication status | Published - 1 Dec 2007 |

Externally published | Yes |

Event | 33rd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2007 - Dornburg, Germany Duration: 21 Jun 2007 → 23 Jun 2007 Conference number: 33 |

### Publication series

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

Publisher | Springer |

Volume | 4769 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Workshop

Workshop | 33rd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2007 |
---|---|

Abbreviated title | WG |

Country/Territory | Germany |

City | Dornburg |

Period | 21/06/07 → 23/06/07 |

## Keywords

- Approximation algorithm
- Undirected graph
- Approximation ratio
- Edge weight
- Minimum weight