On Approximating Restricted Cycle Covers
From MaRDI portal
Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
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
- Approximation and Online Algorithms
- Approximation Algorithms for Restricted Cycle Covers Based on Cycle Decompositions
- On approximating maximum covering cycles in undirected graphs
- Minimum-weight cycle covers and their approximability
- Minimum-Weight Cycle Covers and Their Approximability
- On cycle covers of graphs with bounded pathwidth
- scientific article; zbMATH DE number 475603
- The bounded cycle-cover problem
- Constant-factor approximations for cycle cover problems
- Approximation Algorithms for Min-Max Cycle Cover Problems
Cited in
(21)- An overview of graph covering and partitioning
- On cycle covers of graphs with bounded pathwidth
- An algorithm for the polyhedral cycle cover problem with constraints on the number and length of cycles
- STACS 2005
- A note about shortest cycle covers
- Improved approximation algorithms for cycle and path packings
- Minimum-Weight Cycle Covers and Their Approximability
- A polynomial-time approximation scheme for the Euclidean problem on a cycle cover of a graph
- Approximation Algorithms for Restricted Cycle Covers Based on Cycle Decompositions
- Approximation algorithms for cycle and path partitions in complete graphs
- Minimum-weight cycle covers and their approximability
- Approximately covering by cycles in planar graphs.
- scientific article; zbMATH DE number 1947046 (Why is no real title available?)
- Approximability of the minimum-weight \(k\)-size cycle cover problem
- Polynomial-time approximability of the asymmetric problem of covering a graph by a bounded number of cycles
- Two Approximation Algorithms for ATSP with Strengthened Triangle Inequality
- Polynomial time approximation scheme for single-depot Euclidean capacitated vehicle routing problem
- Covering tours and cycle covers with turn costs: hardness and approximation
- On approximating maximum covering cycles in undirected graphs
- On asymptotically optimal solvability of max \(m\)-\(k\)-cycles cover problem in a normed space
- Approximation and Online Algorithms
This page was built for publication: On Approximating Restricted Cycle Covers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3614154)
