ECCC-Report TR07-011https://eccc.weizmann.ac.il/report/2007/011Comments and Revisions published for TR07-011en-usMon, 29 Jan 2007 12:00:12 +0200
Paper TR07-011
| On Approximating Restricted Cycle Covers |
Bodo Manthey
https://eccc.weizmann.ac.il/report/2007/011A 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 and NP-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.
Mon, 29 Jan 2007 12:00:12 +0200https://eccc.weizmann.ac.il/report/2007/011