Approximation algorithms for restricted cycle covers based on cycle decompositions

Bodo Manthey*

*Corresponding author for this work

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

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 languageEnglish
Title of host publicationGraph-Theoretic Concepts in Computer Science
Subtitle of host publication32nd International Workshop, WG 2006, Bergen, Norway, June 22-24, 2006 Revised Papers
EditorsFedor V. Fomin
Place of PublicationBerlin, Heidelberg
PublisherSpringer
Pages336-347
Number of pages12
ISBN (Electronic)978-3-540-48382-3
ISBN (Print)978-3-540-48381-6
DOIs
Publication statusPublished - 1 Jan 2006
Externally publishedYes
Event32nd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2006 - Bergen, Norway
Duration: 22 Jun 200624 Jun 2006
Conference number: 32

Publication series

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

Workshop

Workshop32nd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2006
Abbreviated titleWG
CountryNorway
CityBergen
Period22/06/0624/06/06

Fingerprint

Dive into the research topics of 'Approximation algorithms for restricted cycle covers based on cycle decompositions'. Together they form a unique fingerprint.

Cite this