caa a22 4500 44580470X CHVBK 20180317145153.0 cr unu---uuuuu 170323e20110601xx s 000 0 eng 10.1007/s00453-009-9349-5 doi (NATIONALLICENCE)springer-10.1007/s00453-009-9349-5 Approximability of Packing Disjoint Cycles [Elektronische Daten] [Zachary Friggstad, Mohammad Salavatipour] 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})$ (Krivelevich etal. in ACM Trans. Algorithms, 2009, to appear). In fact, they proved the same upper bound 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 (Andrews etal. in Proc. of 46th IEEE FOCS, pp. 226-244, 2005; Chuzhoy and Khanna in New hardness results for undirected edge disjoint paths. Manuscript, 2005), we show that the undirected edge-disjoint cycle packing problem is quasi-NP-hard to approximate within ratio of $O(\log^{\frac{1}{2}-\epsilon}n)$ for any constant ε>0. The same result holds for the problem of packing vertex-disjoint cycles. Springer Science+Business Media, LLC, 2009 Approximation nationallicence Hardness of approximation nationallicence Edge-disjoint cycles nationallicence Edge-disjoint paths nationallicence Integrality gap nationallicence Friggstad Zachary Department of Computing Science, University of Alberta, T6G 2E8, Edmonton, Alberta, Canada aut Salavatipour Mohammad Department of Computing Science, University of Alberta, T6G 2E8, Edmonton, Alberta, Canada aut Algorithmica Springer-Verlag 60/2(2011-06-01), 395-400 0178-4617 60:2<395 2011 60 453 https://doi.org/10.1007/s00453-009-9349-5 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-009-9349-5 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Friggstad Zachary Department of Computing Science, University of Alberta, T6G 2E8, Edmonton, Alberta, Canada aut NATIONALLICENCE 700 1- Salavatipour Mohammad Department of Computing Science, University of Alberta, T6G 2E8, Edmonton, Alberta, Canada aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 60/2(2011-06-01), 395-400 0178-4617 60:2<395 2011 60 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer