{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T13:43:20Z","timestamp":1773409400052,"version":"3.50.1"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2007,11,1]],"date-time":"2007-11-01T00:00:00Z","timestamp":1193875200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2007,11]]},"abstract":"<jats:p>\n            The\n            <jats:italic>cycle packing number<\/jats:italic>\n            \u03bd\n            <jats:sub>\n              <jats:italic>e<\/jats:italic>\n            <\/jats:sub>\n            (\n            <jats:italic>G<\/jats:italic>\n            ) of a graph\n            <jats:italic>G<\/jats:italic>\n            is the maximum number of pairwise edge-disjoint cycles in\n            <jats:italic>G<\/jats:italic>\n            . Computing \u03bd\n            <jats:sub>\n              <jats:italic>e<\/jats:italic>\n            <\/jats:sub>\n            (\n            <jats:italic>G<\/jats:italic>\n            ) is an NP-hard problem. We present approximation algorithms for computing \u03bd\n            <jats:sub>\n              <jats:italic>e<\/jats:italic>\n            <\/jats:sub>\n            (\n            <jats:italic>G<\/jats:italic>\n            ) in both undirected and directed graphs. In the undirected case we analyze a variant of the modified greedy algorithm suggested by Caprara et al. [2003] and show that it has approximation ratio \u0398(\u221alog\n            <jats:italic>n<\/jats:italic>\n            ), where\n            <jats:italic>n<\/jats:italic>\n            = |\n            <jats:italic>V<\/jats:italic>\n            (\n            <jats:italic>G<\/jats:italic>\n            )|. This improves upon the previous\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>n<\/jats:italic>\n            ) upper bound for the approximation ratio of this algorithm. In the directed case we present a \u221a\n            <jats:italic>n<\/jats:italic>\n            -approximation algorithm. Finally, we give an\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2\/3<\/jats:sup>\n            )-approximation algorithm for the problem of finding a maximum number of edge-disjoint cycles that intersect a specified subset\n            <jats:italic>S<\/jats:italic>\n            of vertices. We also study generalizations of these problems. Our approximation ratios are the currently best-known ones and, in addition, provide upper bounds on the\n            <jats:italic>integrality gap<\/jats:italic>\n            of standard LP-relaxations of these problems. In addition, we give lower bounds for the integrality gap and approximability of \u03bd\n            <jats:sub>\n              <jats:italic>e<\/jats:italic>\n            <\/jats:sub>\n            (\n            <jats:italic>G<\/jats:italic>\n            ) in directed graphs. Specifically, we prove a lower bound of \u03a9(log\n            <jats:italic>n<\/jats:italic>\n            \/loglog\n            <jats:italic>n<\/jats:italic>\n            ) for the integrality gap of edge-disjoint cycle packing. We also show that it is quasi-NP-hard to approximate \u03bd\n            <jats:sub>\n              <jats:italic>e<\/jats:italic>\n            <\/jats:sub>\n            (\n            <jats:italic>G<\/jats:italic>\n            ) within a factor of\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:sup>1<\/jats:sup>\n            \u2212 \u03b5\n            <jats:italic>n<\/jats:italic>\n            ) for any constant \u03b5 &gt; 0. This improves upon the previously known APX-hardness result for this problem.\n          <\/jats:p>","DOI":"10.1145\/1290672.1290685","type":"journal-article","created":{"date-parts":[[2007,11,30]],"date-time":"2007-11-30T14:24:58Z","timestamp":1196432698000},"page":"48","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":40,"title":["Approximation algorithms and hardness results for cycle packing problems"],"prefix":"10.1145","volume":"3","author":[{"given":"Michael","family":"Krivelevich","sequence":"first","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zeev","family":"Nutov","sequence":"additional","affiliation":[{"name":"Open University of Israel, Tel Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mohammad R.","family":"Salavatipour","sequence":"additional","affiliation":[{"name":"University of Alberta, Edmonton, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jacques","family":"Verstraete","sequence":"additional","affiliation":[{"name":"University of Waterloo, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Raphael","family":"Yuster","sequence":"additional","affiliation":[{"name":"University of Haifa, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2007,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.41"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Bafna V. Berman P. and Fujito T. 1995. Constant ratio approximation of the weighted feedback vertex set problem for undirected graphs. In Proceedings of the 6th International Symposium Algorithms and Computation (ISAAC). Lecture Notes in Computer Science Springer 142--151.   Bafna V. Berman P. and Fujito T. 1995. Constant ratio approximation of the weighted feedback vertex set problem for undirected graphs. In Proceedings of the 6th International Symposium Algorithms and Computation (ISAAC). Lecture Notes in Computer Science Springer 142--151.","DOI":"10.1007\/BFb0015417"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548302005461"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 10th Annual Conference on Uncertainty in Artificial Intelligence (July 29--31","author":"Becker A.","unstructured":"Becker , A. , and Geiger , D . 1994. Approximation algorithms for the loop cutset problem . In Proceedings of the 10th Annual Conference on Uncertainty in Artificial Intelligence (July 29--31 , Seattle, WA). 60--68. Becker, A., and Geiger, D. 1994. Approximation algorithms for the loop cutset problem. In Proceedings of the 10th Annual Conference on Uncertainty in Artificial Intelligence (July 29--31, Seattle, WA). 60--68."},{"key":"e_1_2_1_7_1","volume-title":"Extremal Graph Theory","author":"Bollob\u00e1s B.","unstructured":"Bollob\u00e1s , B. 2004. Extremal Graph Theory . Dover , New York . Bollob\u00e1s, B. 2004. Extremal Graph Theory. Dover, New York."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70495-3"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(199711)26:3%3C165::AID-JGT7%3E3.3.CO;2-R"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00052-X"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics","author":"Chekuri C.","unstructured":"Chekuri , C. , and Khanna , S . 2003. Edge disjoint paths revisited . In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics , Philadelphia, PA, 628--637. Chekuri, C., and Khanna, S. 2003. Edge disjoint paths revisited. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics, Philadelphia, PA, 628--637."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2006.v002a007"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(98)00021-2"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129737"},{"key":"e_1_2_1_15_1","unstructured":"Erd\u0151s P. and Sachs H. 1963. Regulare graphen gegebener taillenweite mit minimaler knotenzahl. Wiss. Z. Tech. Rep. Martin-Luther Univ. Halle-Wittenberg Math.-Natur. Reihe 12.  Erd\u0151s P. and Sachs H. 1963. Regulare graphen gegebener taillenweite mit minimaler knotenzahl. Wiss. Z. Tech. Rep. Martin-Luther Univ. Halle-Wittenberg Math.-Natur. Reihe 12."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009191"},{"key":"e_1_2_1_17_1","unstructured":"Friggstad Z. and Salavatipour M. 2006. unpublished manuscript.  Friggstad Z. and Salavatipour M. 2006. unpublished manuscript."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00066-7"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.10.037"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01215920"},{"key":"e_1_2_1_21_1","first-page":"2","article-title":"New upper bounds on the order of cages","volume":"4","author":"Lazebnik F.","year":"1997","unstructured":"Lazebnik , F. , Ustimenko , V. A. , and Woldar , A. J. 1997 . New upper bounds on the order of cages . Electr. J. Comb. 4 , 2 . Lazebnik, F., Ustimenko, V. A., and Woldar, A. J. 1997. New upper bounds on the order of cages. Electr. J. Comb. 4, 2.","journal-title":"Electr. J. Comb."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1661"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795280895"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200760"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 379--380","author":"Varadarajan K.","unstructured":"Varadarajan , K. , and Venkataraman , G . 2004. Graph decomposition and a greedy algorithm for edge-disjoint paths . In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 379--380 . Varadarajan, K., and Venkataraman, G. 2004. Graph decomposition and a greedy algorithm for edge-disjoint paths. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 379--380."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1290672.1290685","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1290672.1290685","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T14:52:25Z","timestamp":1750258345000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1290672.1290685"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,11]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2007,11]]}},"alternative-id":["10.1145\/1290672.1290685"],"URL":"https:\/\/doi.org\/10.1145\/1290672.1290685","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,11]]},"assertion":[{"value":"2007-11-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}