On approximating restricted cycle covers

Research output: Contribution to journalArticleAcademicpeer-review

7 Citations (Scopus)
25 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. 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. 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 within a factor of 2 for undirected graphs and within a factor of $8/3$ in the case of directed graphs. This holds for arbitrary sets L.
Original languageEnglish
Pages (from-to)181-206
Number of pages26
JournalSIAM journal on computing
Volume38
Issue number1
DOIs
Publication statusPublished - 2008

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

Cite this