Minimum-weight cycle covers and their approximability

Research output: Contribution to journalArticleAcademicpeer-review

8 Citations (Scopus)
40 Downloads (Pure)

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 \subseteq \Bbb{N}$. We investigate how well $L$-cycle covers of minimum weight can be approximated. For undirected graphs, we devise non-constructive polynomial-time approximation algorithms that achieve constant approximation ratios for all sets $L$. On the other hand, we prove that the problem cannot be approximated with a factor of $2-\varepsilon$ for certain sets $L$. For directed graphs, we devise non-constructive polynomial-time approximation algorithms that achieve approximation ratios of $O(n)$, where $n$ is the number of vertices. This is asymptotically optimal: We show that the problem cannot be approximated with a factor of $o(n)$ for certain sets $L$. 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
Pages (from-to)1470-1480
Number of pages11
JournalDiscrete applied mathematics
Volume157
Issue number7
DOIs
Publication statusPublished - Apr 2009

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

Cite this