On approximating restricted cycle covers

Bodo Manthey*

*Corresponding author for this work

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

2 Citations (Scopus)


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. A special case of L-cycle covers are k-cycle covers for k ∈ ℕ, where the length of each cycle must be at least k. The weight of a cycle cover of an edge-weighted graph is the sum of the weights of its edges. We come close to settling the complexity and approximability of computing L-cycle covers. On the one hand, we show that for almost all L, computing L-cycle covers of maximum weight in directed and undirected graphs is APX-hard and NP-hard. Most of our hardness results hold even if the edge weights are restricted to zero and one. On the other hand, we show that the problem of computing L-cycle covers of maximum weight can be approximated with factor 2.5 for undirected graphs and with factor 3 in the case of directed graphs. Finally, we show that 4-cycle covers of maximum weight in graphs with edge weights zero and one can be computed in polynomial time. As a by-product, we show that the problem of computing minimum vertex covers in λ-regular graphs is APX-complete for every λ ≥ 3.

Original languageEnglish
Title of host publicationApproximation and Online Algorithms
Subtitle of host publicationThird International Workshop, WAOA 2005, Palma de Mallorca, Spain, October 6-7, 2005, Revised Papers
EditorsThomas Erlebach, Giuseppe Persinao
Place of PublicationBerlin, Heidelberg
Number of pages14
ISBN (Electronic)978-3-540-32208-5
ISBN (Print)978-3-540-32207-8
Publication statusPublished - 10 Jul 2006
Externally publishedYes
Event3rd International Workshop on Approximation and Online Algorithms, WAOA 2005 - Hotel Tryp Bellver, Palma de Mallorca, Spain
Duration: 6 Oct 20057 Oct 2005
Conference number: 3

Publication series

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


Workshop3rd International Workshop on Approximation and Online Algorithms, WAOA 2005
Abbreviated titleWAOA
CityPalma de Mallorca

Fingerprint Dive into the research topics of 'On approximating restricted cycle covers'. Together they form a unique fingerprint.

Cite this