On approximating restricted cycle covers

Manthey, Bodo (2008) On approximating restricted cycle covers. SIAM Journal on Computing, 38 (1). pp. 181-206. ISSN 0097-5397

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

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 $\mathsf{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$
Item Type:	Article
Copyright:	© 2008 Society for Industrial and Applied Mathematics
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/79439
Official URL:	http://dx.doi.org/10.1137/060676003
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Repository Staff Only: item control page