zbMATH — the first resource for mathematics

Approximability of packing disjoint cycles. (English) Zbl 1193.68286
Tokuyama, Takeshi (ed.), Algorithms and computation. 18th international symposium, ISAAC 2007, Sendai, Japan, December 17–19, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-77118-0/pbk). Lecture Notes in Computer Science 4835, 304-315 (2007).
Summary: Given a graph \(G\), the edge-disjoint cycle packing problem is to find the largest set of cycles of which no two share an edge. For undirected graphs, the best known approximation algorithm has ratio \(O(\sqrt{\log n})\). In fact, the same upper bound was proved for the integrality gap of this problem by presenting a simple greedy algorithm. Here we show that this is almost best possible. By modifying integrality gap and hardness results for the edge-disjoint paths problem, we show that the undirected edge-disjoint cycle packing problem has an integrality gap of \(\Omega(\frac{\sqrt{\log n}}{\log\log n})\) and furthermore it is quasi-NP-hard to approximate the edge-disjoint cycle problem within ratio of \(O(\log^{\frac{1}{2}-\epsilon} n)\) for any constant \(\epsilon > 0\). The same results hold for the problem of packing vertex-disjoint cycles.
For the entire collection see [Zbl 1136.68011].

68W25 Approximation algorithms
05B40 Combinatorial aspects of packing and covering
05C38 Paths and cycles
05C85 Graph algorithms (graph-theoretic aspects)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDF BibTeX Cite
Full Text: DOI