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

[img] PDF
Restricted to UT campus only
: Request a copy
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
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/79439
Official URL:https://doi.org/10.1137/060676003
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page