Minimum-weight cycle covers and their approximability

Bodo Manthey*

*Corresponding author for this work

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

1 Citation (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 ⊆ ℕ. We investigate how well L-cycle covers of minimum weight can be approximated. For undirected graphs, we devise a polynomial-time approximation algorithm that achieves a constant approximation ratio for all sets L. On the other hand, we prove that the problem cannot be approximated within a factor of 2 - ε for certain sets L. For directed graphs, we present a polynomial-time approximation algorithm that achieves an approximation ratio of O(n), where n is the number of vertices. This is asymptotically optimal: We show that the problem cannot be approximated within a factor of o(n). To contrast the results for cycle covers of minimum weight, we show that the problem of computing L-cycle covers of maximum weight can, at least in principle, be approximated arbitrarily well.

Original languageEnglish
Title of host publicationGraph-Theoretic Concepts in Computer Science
Subtitle of host publication33rd International Workshop, WG 2007, Revised Papers
PublisherSpringer
Pages178-189
Number of pages12
ISBN (Electronic)978-3-540-74839-7
ISBN (Print)978-3-540-74838-0
DOIs
Publication statusPublished - 1 Dec 2007
Externally publishedYes
Event33rd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2007 - Dornburg, Germany
Duration: 21 Jun 200723 Jun 2007
Conference number: 33

Publication series

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

Workshop

Workshop33rd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2007
Abbreviated titleWG
CountryGermany
CityDornburg
Period21/06/0723/06/07

Keywords

  • Approximation algorithm
  • Undirected graph
  • Approximation ratio
  • Edge weight
  • Minimum weight

Fingerprint Dive into the research topics of 'Minimum-weight cycle covers and their approximability'. Together they form a unique fingerprint.

  • Cite this

    Manthey, B. (2007). Minimum-weight cycle covers and their approximability. In Graph-Theoretic Concepts in Computer Science: 33rd International Workshop, WG 2007, Revised Papers (pp. 178-189). (Lecture Notes in Computer Science; Vol. 4769). Springer. https://doi.org/10.1007/978-3-540-74839-7_18