Approximation Algorithms for Restricted Cycle Covers Based on Cycle Decompositions
From MaRDI portal
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 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.
Recommendations
Cited in
(8)- Minimum-weight cycle covers and their approximability
- On the Cycle Augmentation Problem: hardness and approximation algorithms
- Covering tours and cycle covers with turn costs: hardness and approximation
- Minimum-Weight Cycle Covers and Their Approximability
- On Approximating Restricted Cycle Covers
- A polynomial-time approximation scheme for the Euclidean problem on a cycle cover of a graph
- Approximation and Online Algorithms
- Hardness of approximation in p via short cycle removal: cycle detection, distance oracles, and beyond
This page was built for publication: Approximation Algorithms for Restricted Cycle Covers Based on Cycle Decompositions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3522970)
