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)

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. 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
PublisherSpringer
Pages282-295
Number of pages14
ISBN (Electronic)978-3-540-32208-5
ISBN (Print)978-3-540-32207-8
DOIs
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
PublisherSpringer
Volume3879
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Workshop

Workshop3rd International Workshop on Approximation and Online Algorithms, WAOA 2005
Abbreviated titleWAOA
CountrySpain
CityPalma de Mallorca
Period6/10/057/10/05

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

  • Cite this

    Manthey, B. (2006). On approximating restricted cycle covers. In T. Erlebach, & G. Persinao (Eds.), Approximation and Online Algorithms: Third International Workshop, WAOA 2005, Palma de Mallorca, Spain, October 6-7, 2005, Revised Papers (pp. 282-295). (Lecture Notes in Computer Science; Vol. 3879). Berlin, Heidelberg: Springer. https://doi.org/10.1007/11671411_22