Abstract
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 et al. 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 et al. 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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Andrews, M., Chuzhoy, J., Khanna, S., Zhang, L.: Hardness of the undirected edge-disjoint paths problem with congestion. In: Proc. of 46th IEEE FOCS, pp. 226–244 (2005)
Andrews, M., Zhang, L.: Hardness of the undirected edge-disjoint paths problem. In: Proc. of 37th ACM STOC, pp. 276–283. ACM Press, New York (2005)
Balister, P.: Packing digraphs with directed closed trials. Comb. Probab. Comput. 12, 1–15 (2003)
Caprara, A., Panconesi, A., Rizzi, R.: Packing cycles in undirected graphs. J. Algorithms 48, 239–256 (2003)
Chekuri, C., Khanna, S., Shepherd, B.: An \(O(\sqrt{n})\) approximation and integrality gap for disjoint paths and UFP. Theory Comput. 2, 137–146 (2006)
Chuzhoy, J., Guha, S., Halperin, E., Khanna, S., Kortsarz, G., Krauthgamer, R., Naor, S.: Tight lower bounds for the asymmetric k-center problem. J. ACM 52(4), 538–551 (2005)
Chuzhoy, J., Khanna, S.: New hardness results for undirected edge disjoint paths. Manuscript (2005)
Dor, D., Tarsi, M.: Graph decomposition is NPC—A complete proof of Holyer’s conjecture. In: Proc. of 20th ACM STOC, pp. 252–263. ACM Press, New York (1992)
Friggstad, Z., Salavatipour, M.R.: Approximability of packing disjoint cycles. In: Proc. of the 18th Int. Symp. on Algorithms and Computation (ISAAC) 2007. LNCS, pp. 304–315. Springer, Berlin (2007)
Guruswami, V., Khanna, S., Rajaraman, R., Shepherd, B., Yannakakis, M.: Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. J. Comput. Syst. Sci. 67(3), 473–496 (2003). Earlier version in STOC’99
Halldorsson, M.M., Kortsarz, G., Radhakrishnan, J., Sivasubramanian, S.: Complete partitions of graphs. Combinatorica 27(5), 519–550 (2007)
Kleinberg, J.: Approximation algorithms for disjoint paths problems. PhD. Thesis, MIT, Cambridge, MA, May 1996
Krivelevich, M., Nutov, Z., Salavatipour, M.R., Verstraete, J., Yuster, R.: Approximation algorithms and hardness results for cycle packing problems. ACM Trans. Algorithms 3(4), 48 (2007)
Samorodnitsky, A., Trevisan, L.: A PCP characterization of NP with optimal amortized query complexity. In: Proc. of 32nd ACM STOC, pp. 191–199. ACM Press, New York (2000)
Seymour, P.D.: Packing directed circuits fractionally. Combinatorica 15, 281–288 (1995)
Varadarajan, K.R., Venkataraman, G.: Graph decomposition and a greedy algorithm for edge-disjoint paths. In: Proc. of 15 ACM-SIAM SODA, pp. 379–380 (2004)
Author information
Authors and Affiliations
Corresponding author
Additional information
A preliminary version appeared [9] in Proceedings of ISAAC 2007.
The first author was supported by NSERC and iCore scholarships and the 2nd author was supported by NSERC and an Alberta Ingenuity New Faculty award.
Rights and permissions
About this article
Cite this article
Friggstad, Z., Salavatipour, M.R. Approximability of Packing Disjoint Cycles. Algorithmica 60, 395–400 (2011). https://doi.org/10.1007/s00453-009-9349-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-009-9349-5