## Abstract

A cycle cover of a directed graph is a collection of node disjoint cycles such that every node is part of exactly one cycle. A k-cycle cover is a cycle cover in which every cycle has length at least k. While deciding whether a directed graph has a 2-cycle cover is solvable in polynomial time, deciding whether it has a 3-cycle cover is already NP-complete. Given a directed graph with nonnegative edge weights, a maximum weight 2-cycle cover can be computed in polynomial time, too. We call the corresponding optimization problem of finding a maximum weight 3-cycle cover Max-3-DCC. In this paper we present two polynomial time approximation algorithms for Max-3-DCC. The heavier of the 3-cycle covers computed by these algorithms has at least a fraction of ⅗ − ε, for any ε > 0, of the weight of a maximum weight 3-cycle cover. As a lower bound, we prove that Max-3-DCC is APX-complete, even if the weights fulfil the triangle inequality.

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

Title of host publication | Approximation Algorithms for Combinatorial Optimization |

Subtitle of host publication | 5th International Workshop, APPROX 2002 Rome, Italy, September 17–21, 2002 Proceedings |

Editors | Stefano Leonardi, Klaus Jansen, Vijay Vazirani |

Place of Publication | Berlin, Heidelberg |

Publisher | Springer |

Pages | 40-50 |

Number of pages | 11 |

ISBN (Electronic) | 978-3-540-45753-4 |

ISBN (Print) | 978-3-540-44186-1 |

DOIs | |

Publication status | Published - 1 Jan 2002 |

Externally published | Yes |

Event | 5th International Workshop On Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2002 - Universita' di Roma "La Sapienza", Rome, Italy Duration: 17 Sep 2002 → 21 Sep 2002 Conference number: 5 http://users.diag.uniroma1.it/algo02/approx02/ |

### Publication series

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

Publisher | Springer |

Volume | 2462 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 5th International Workshop On Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2002 |
---|---|

Abbreviated title | APPROX 2002 |

Country/Territory | Italy |

City | Rome |

Period | 17/09/02 → 21/09/02 |

Internet address |