Name
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. A special case of L-cycle covers are k-cycle covers for k∈ℕ, where the length of each cycle must be at least k. 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 with factor 2.5 for undirected graphs and with factor 3 in the case of directed graphs. Finally, we show that 4-cycle covers of maximum weight in graphs with edge weights zero and one can be computed in polynomial time. As a by-product, we show that the problem of computing minimum vertex covers in λ-regular graphs is APX-complete for every λ≥3. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1137/060676003 | Electronic Colloquium on Computational Complexity |
Keywords | DocType | Volume |
edge-weighted graph,edge weight,hardness result,undirected graph,cycle cover,restricted cycle covers,maximum weight,arbitrary set | Conference | 38 |
Issue | ISSN | ISBN |
1 | 0097-5397 | 3-540-32207-8 |
Citations | PageRank | References |
10 | 0.62 | 31 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Bodo Manthey | 1 | 63 | 5.38 |