Two approximation algorithms for 3-cycle covers

Markus Bläser, Bodo Manthey

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

12 Citations (Scopus)

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 languageEnglish
Title of host publicationApproximation Algorithms for Combinatorial Optimization
Subtitle of host publication5th International Workshop, APPROX 2002 Rome, Italy, September 17–21, 2002 Proceedings
EditorsStefano Leonardi, Klaus Jansen, Vijay Vazirani
Place of PublicationBerlin, Heidelberg
PublisherSpringer
Pages40-50
Number of pages11
ISBN (Electronic)978-3-540-45753-4
ISBN (Print)978-3-540-44186-1
DOIs
Publication statusPublished - 1 Jan 2002
Externally publishedYes
Event5th International Workshop On Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2002 - Universita' di Roma "La Sapienza", Rome, Italy
Duration: 17 Sep 200221 Sep 2002
Conference number: 5
http://users.diag.uniroma1.it/algo02/approx02/

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume2462
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference5th International Workshop On Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2002
Abbreviated titleAPPROX 2002
CountryItaly
CityRome
Period17/09/0221/09/02
Internet address

Fingerprint

Dive into the research topics of 'Two approximation algorithms for 3-cycle covers'. Together they form a unique fingerprint.

Cite this