{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:32:38Z","timestamp":1787322758565,"version":"build-2736575974"},"reference-count":44,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/100011199","name":"FP7 Ideas: European Research Council","doi-asserted-by":"publisher","award":["306992"],"award-info":[{"award-number":["306992"]}],"id":[{"id":"10.13039\/100011199","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2019,1]]},"abstract":"<jats:p>The Cycle Packing problem asks whether a given undirected graph $G=(V,E)$ contains $k$ vertex-disjoint cycles. Since the publication of the classic Erd\u00f6s--P\u00f3sa theorem in 1965, this problem received significant attention in the fields of graph theory and algorithm design. In particular, this problem is one of the first problems studied in the framework of parameterized complexity. The nonuniform fixed-parameter tractability of Cycle Packing follows from the Robertson--Seymour theorem, a fact already observed by Fellows and Langston in the 1980s. In 1994, Bodlaender showed that Cycle Packing can be solved in time $2^{\\mathcal{O}(k^2)}\\cdot |V|$ using exponential space. In the case a solution exists, Bodlaender's algorithm also outputs a solution (in the same time). It has later become common knowledge that Cycle Packing admits a $2^{\\mathcal{O}(k\\log^2k)}\\cdot |V|$-time (deterministic) algorithm using exponential space, which is a consequence of the Erd\u00f6s--P\u00f3sa theorem. Nowadays, the design of this algorithm is given as an exercise in textbooks on parameterized complexity. Yet, no algorithm that runs in time $2^{o(k\\log^2k)}\\cdot |V|^{\\mathcal{O}(1)}$, beating the bound $2^{\\mathcal{O}(k\\log^2k)}\\cdot |V|^{\\mathcal{O}(1)}$, has been found. In light of this, it seems natural to ask whetherthe $2^{\\mathcal{O}(k\\log^2k)}\\cdot |V|^{\\mathcal{O}(1)}$ bound is essentially optimal. In this paper, we answer this question negatively by developing a $2^{\\mathcal{O}(\\frac{k\\log^2k}{\\log\\log k})}\\cdot |V|$-time (deterministic) algorithm for Cycle Packing. In the case a solution exists, our algorithm also outputs a solution (in the same time). Moreover, apart from beating the bound $2^{\\mathcal{O}(k\\log^2k)}\\cdot |V|^{\\mathcal{O}(1)}$, our algorithm runs in time linear in $|V|$, and its space complexity is polynomial in the input size.<\/jats:p>","DOI":"10.1137\/17m1150037","type":"journal-article","created":{"date-parts":[[2019,7,2]],"date-time":"2019-07-02T14:51:01Z","timestamp":1562079061000},"page":"1194-1215","source":"Crossref","is-referenced-by-count":5,"title":["Packing Cycles Faster Than Erdos--Posa"],"prefix":"10.1137","volume":"33","author":[{"given":"Daniel","family":"Lokshtanov","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Amer E.","family":"Mouawad","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Meirav","family":"Zehavi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2019,7,2]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1007\/s003730200002"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796305109"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054194000049"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.09.006"},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"H. L. Bodlaender, E. Penninkx, and R. B. Tan,\n                      A linear kernel for the $k$-disjoint cycle problem on planar graphs\n                      , in Proceedings of the 19th International Symposium on Algorithms and Computation, Gold Coast, Australia, Lecture Notes in Comput. Sci. 5369, S. Hong, H. Nagamochi, and T. Fukunaga, eds., Springer, New York, 2008, pp. 306-317,https:\/\/doi.org\/10.1007\/978-3-540-92182-0_29.","DOI":"10.1007\/978-3-540-92182-0_29"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.04.039"},{"key":"atypb7","first-page":"291","author":"Chekuri C.","year":"2013","journal-title":"New York"},{"key":"atypb8","first-page":"63","author":"Chekuri C.","year":"2016","journal-title":"J. ACM"},{"key":"atypb9","first-page":"645","author":"Chuzhoy J.","year":"2015","journal-title":"New York"},{"key":"atypb10","unstructured":"J. Chuzhoy,\n                      Excluded grid theorem: Improved and simplified\n                      , in Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory, Reykjavik, Iceland, R. Pagh, ed., LIPIcs 53, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016,https:\/\/doi.org\/10.4230\/LIPIcs.SWAT.2016.31."},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"M. Cygan, F. V. Fomin, \u0141. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh,\n                      Parameterized Algorithms\n                      , Springer, New York, 2015.","DOI":"10.1007\/978-3-319-21275-3"},{"key":"atypb12","first-page":"150","author":"Cygan M.","year":"2011","journal-title":"Washington, DC"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"R. Diestel,\n                      Graph Theory\n                      , 4th ed., Grad. Texts in Math. 173, Springer, New York, 2012.","DOI":"10.1007\/978-3-662-53622-3_7"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2012.02.004"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows,\n                      Fundamentals of Parameterized Complexity\n                      , Springer, New York, 2013.","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1965-035-8"},{"key":"atypb17","first-page":"748","author":"Fomin F. V.","year":"2011","journal-title":"Philadelphia"},{"key":"atypb18","first-page":"503","author":"Fomin F. V.","year":"2010","journal-title":"Philadelphia"},{"key":"atypb19","doi-asserted-by":"crossref","unstructured":"F. V. Fomin, D. Lokshtanov, S. Saurabh, and M. Zehavi,\n                      Kernelization: Theory of Parameterized Preprocessing\n                      , Cambridge University Press, Cambridge, 2018.","DOI":"10.1017\/9781107415157"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-009-9349-5"},{"key":"atypb21","unstructured":"M. R. Garey and D. S. Johnson,\n                      Computers and Intractability\n                      , Vol. 29, W. H. Freeman, New York, 2002."},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"M. Grohe and M. Gr\u00fcber,\n                      Parameterized approximability of the disjoint cycle problem\n                      , in Proceedings of the 34th International Colloquium Automata, Languages and Programming, Wroclaw, Poland, L. Arge, C. Cachin, T. Jurdzinski, and A. Tarlecki, eds., Lecture Notes in Comput. Sci. 4596, Springer, New York, 2007, pp. 363-374,https:\/\/doi.org\/10.1007\/978-3-540-73420-8_33.","DOI":"10.1007\/978-3-540-73420-8_33"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1137\/0207033"},{"key":"atypb25","doi-asserted-by":"crossref","unstructured":"F. Joos,\n                      Parity linkage and the Erd\u00f6s-P\u00f3sa property of odd cycles through prescribed vertices in highly connected graphs\n                      , in Proceedings of Graph-Theoretic Concepts in Computer Science-41st International Workshop, Garching, Germany, E. W. Mayr, ed., Lecture Notes in Comput. Sci. 9224, Springer, New York, 2015, pp. 339-350,https:\/\/doi.org\/10.1007\/978-3-662-53174-7_24.","DOI":"10.1007\/978-3-662-53174-7_24"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-013-2865-6"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2011.03.004"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2011.12.001"},{"key":"atypb29","first-page":"365","author":"Kawarabayashi K.","year":"2013","journal-title":"Philadelphia"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2006.07.008"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-009-2178-y"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2005.08.001"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1145\/1290672.1290685"},{"key":"atypb34","first-page":"224","author":"Lokshtanov D.","year":"2017","journal-title":"Montreal, QC, Canada"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9630-x"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2012.05.004"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1145\/1159892.1159898"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1007\/s004930100024"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050056"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(86)90030-4"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1137\/070697781"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1007\/s004930100028"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-012-9412-5"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1150037","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:25:18Z","timestamp":1787318718000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1150037"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1]]},"references-count":44,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,1]]}},"alternative-id":["10.1137\/17M1150037"],"URL":"https:\/\/doi.org\/10.1137\/17m1150037","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1]]}}}