Approximation algorithms and hardness results for cycle packing problems

DOI10.1145/1290672.1290685zbMath1446.68121MaRDI QIDQ4962688

Michael Krivelevich, Mohammad R. Salavatipour, Jacques Verstraete, Raphael Yuster, Zeev Nutov

Publication date: 5 November 2018

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1290672.1290685

zbMATH Keywords

approximation algorithms; hardness of approximation; integrality gap; cycle packing; edge-disjoint

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C38: Paths and cycles

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68W25: Approximation algorithms

Related Items

Maximum cycle packing using SPR-trees, Cycle decompositions and constructive characterizations, Packing Euler graphs with traces, Packing Arc-Disjoint Cycles in Tournaments, Packing Cycles Faster Than Erdos--Posa, Approximability of Packing Disjoint Cycles, Unnamed Item, Packing arc-disjoint cycles in oriented graphs, Edge-disjoint odd cycles in 4-edge-connected graphs, A note on disjoint cycles, Packing cycles exactly in polynomial time, Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem, Packing cycles through prescribed vertices under modularity constraints, Approximability of packing disjoint cycles, Approximation algorithms for grooming in optical network design, Disjoint cycles intersecting a set of vertices, Induced packing of odd cycles in planar graphs, Packing edge-disjoint cycles in graphs and the cyclomatic number, Packing disjoint cycles over vertex cuts, Half-integral packing of odd cycles through prescribed vertices, Packing cycles through prescribed vertices, A complexity and approximation framework for the maximization scaffolding problem, Minimum degree conditions for vertex-disjoint even cycles in large graphs, Packing arc-disjoint cycles in tournaments, Disjoint Even Cycles Packing