Minimum-weight cycle covers and their approximability

Manthey, B. (2009) Minimum-weight cycle covers and their approximability. Discrete Applied Mathematics, 157 (7). pp. 1470-1480. ISSN 0166-218X

PDF
Restricted to UT campus only: Request a copy
808Kb

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.
Item Type:	Article
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP)
Link to this item:	http://purl.utwente.nl/publications/68062
Official URL:	http://dx.doi.org/10.1016/j.dam.2008.10.005
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Repository Staff Only: item control page