{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T20:06:51Z","timestamp":1773518811938,"version":"3.50.1"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"1","funder":[{"DOI":"10.13039\/501100005416","name":"Research Council of Norway","doi-asserted-by":"crossref","award":["314528"],"award-info":[{"award-number":["314528"]}],"id":[{"id":"10.13039\/501100005416","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Franco-Norwegian AURORA project","award":["349476"],"award-info":[{"award-number":["349476"]}]},{"name":"UKRI EPSRC","award":["EP\/V044621\/1"],"award-info":[{"award-number":["EP\/V044621\/1"]}]},{"name":"Swarnajayanti Fellowship","award":["DST\/SJF\/MSA-01\/2017-18"],"award-info":[{"award-number":["DST\/SJF\/MSA-01\/2017-18"]}]},{"name":"ERC Horizon 2020 research and innovation programme","award":["819416"],"award-info":[{"award-number":["819416"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2026,1,31]]},"abstract":"\n Cycle packing is a fundamental problem in optimization, graph theory, and algorithms. Motivated by recent advancements in finding vertex-disjoint paths between a specified set of vertices that either minimize the total length of the paths [Bj\u00f6rklund and Husfeldt, ICALP 2014; Mari et al., SODA 2024] or request the paths to be shortest [Lochet, SODA 2021], we consider the following cycle packing problems:\n Min-Sum Cycle Packing<\/jats:sc>\n and\n Shortest Cycle Packing<\/jats:sc>\n .\n <\/jats:p>\n \n In\n Min-Sum Cycle Packing<\/jats:sc>\n , we try to find, in a weighted undirected graph,\n \n \\( k \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n vertex-disjoint cycles of minimum total weight. Our first main result is an algorithm that, for any fixed\n \n \\( k \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , solves the problem in polynomial time. We complement this result by establishing the W[1]-hardness of\n Min-Sum Cycle Packing<\/jats:sc>\n parameterized by\n \n \\( k \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . The same results hold for the version of the problem where the task is to find\n \n \\( k \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n edge-disjoint cycles.\n <\/jats:p>\n \n Our second main result concerns\n Shortest Cycle Packing<\/jats:sc>\n , which is a special case of\n Min-Sum Cycle Packing<\/jats:sc>\n that asks to find a packing of\n \n \\( k \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n shortest cycles in a graph. We prove this problem to be Fixed-Parameter Tractable (FPT) when parameterized by\n \n \\( k \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n on weighted planar graphs. We also obtain a polynomial kernel for the edge-disjoint variant of the problem on planar graphs. Whether\n Min-Sum Cycle Packing<\/jats:sc>\n is FPT on planar graphs, or\n Shortest Cycle Packing<\/jats:sc>\n on general graphs, remains open.\n <\/jats:p>","DOI":"10.1145\/3765285","type":"journal-article","created":{"date-parts":[[2025,9,1]],"date-time":"2025-09-01T13:01:13Z","timestamp":1756731673000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Packing Short Cycles"],"prefix":"10.1145","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-0705-972X","authenticated-orcid":false,"given":"Matthias","family":"Bentert","sequence":"first","affiliation":[{"name":"Universitetet i Bergen, Bergen, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1955-4612","authenticated-orcid":false,"given":"Fedor","family":"V. Fomin","sequence":"additional","affiliation":[{"name":"Universitetet i Bergen, Bergen, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2619-2990","authenticated-orcid":false,"given":"Petr","family":"A. Golovach","sequence":"additional","affiliation":[{"name":"Universitetet i Bergen, Bergen, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0861-6515","authenticated-orcid":false,"given":"Tuukka","family":"Korhonen","sequence":"additional","affiliation":[{"name":"University of Copenhagen, Kobenhavn, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8711-1170","authenticated-orcid":false,"given":"William","family":"Lochet","sequence":"additional","affiliation":[{"name":"Universit\u00e9 de Montpellier, Montpellier, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6213-8687","authenticated-orcid":false,"given":"Fahad","family":"Panolan","sequence":"additional","affiliation":[{"name":"University of Leeds, Leeds, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2116-6048","authenticated-orcid":false,"given":"M. S.","family":"Ramanujan","sequence":"additional","affiliation":[{"name":"University of Warwick, Coventry, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7847-6402","authenticated-orcid":false,"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[{"name":"The Institute of Mathematical Sciences, Chennai, India and Universitetet i Bergen, Bergen, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9436-7310","authenticated-orcid":false,"given":"Kirill","family":"Simonov","sequence":"additional","affiliation":[{"name":"University of Bergen, Bergen, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,10,7]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"crossref","DOI":"10.1090\/conm\/098","volume-title":"Every Planar Map Is Four Colorable","author":"Appel Kenneth","year":"1989","unstructured":"Kenneth Appel and Wolfgang Haken. 1989. Every Planar Map Is Four Colorable. American Mathematical Society."},{"issue":"3","key":"e_1_3_2_3_2","doi-asserted-by":"crossref","first-page":"1674","DOI":"10.1137\/22M1527398","article-title":"Using a geometric lens to find \\( k \\) -disjoint shortest paths","volume":"37","author":"Bentert Matthias","year":"2023","unstructured":"Matthias Bentert, Andr\u00e9 Nichterlein, Malte Renken, and Philipp Zschoche. 2023. Using a geometric lens to find \\( k \\) -disjoint shortest paths. SIAM Journal on Discrete Mathematics 37, 3 (2023), 1674\u20131703.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-014-0398-5"},{"key":"e_1_3_2_5_2","doi-asserted-by":"crossref","unstructured":"Andreas Bj\u00f6rklund and Thore Husfeldt. 2019. Shortest two disjoint paths in polynomial time. SIAM Journal on Computing 48 6 (2019) 1698\u20131710.","DOI":"10.1137\/18M1223034"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/2973749"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.04.039"},{"key":"e_1_3_2_8_2","first-page":"227","volume-title":"Proceedings of the 23rd Annual European Symposium Algorithms (ESA)","author":"Borradaile Glencora","year":"2015","unstructured":"Glencora Borradaile, Amir Nayyeri, and Farzad Zafarani. 2015. Towards single face shortest vertex-disjoint paths in undirected planar graphs. In Proceedings of the 23rd Annual European Symposium Algorithms (ESA). Springer, 227\u2013238."},{"key":"e_1_3_2_9_2","first-page":"239","volume-title":"Proceedings of the 2nd International Workshop on Parameterized and Exact Computation (IWPEC)","author":"Cai Leizhen","year":"2006","unstructured":"Leizhen Cai, Siu Man Chan, and Siu On Chan. 2006. Random separation: A new method for solving fixed-cardinality optimization problems. In Proceedings of the 2nd International Workshop on Parameterized and Exact Computation (IWPEC). Springer, 239\u2013250."},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2001.1178"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/506147.506148"},{"issue":"2","key":"e_1_3_2_12_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1921659.1921665","article-title":"Shortest vertex-disjoint two-face paths in planar graphs","volume":"7","author":"De Verdi\u00e8re \u00c9ric Colin","year":"2011","unstructured":"\u00c9ric Colin De Verdi\u00e8re and Alexander Schrijver. 2011. Shortest vertex-disjoint two-face paths in planar graphs. ACM Transactions on Algorithms 7, 2 (2011), 1\u201312.","journal-title":"ACM Transactions on Algorithms"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3"},{"key":"e_1_3_2_14_2","first-page":"1","volume-title":"Proceedings of the 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS)","volume":"19","author":"Datta Samir","year":"2018","unstructured":"Samir Datta, Siddharth Iyer, Raghav Kulkarni, and Anish Mukherjee. 2018. Shortest \\( k \\) -disjoint paths via determinants. In Proceedings of the 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS). Schloss Dagstuhl\u2014Leibniz-Zentrum F\u00fcr Informatik, Article 19, 1\u201321."},{"key":"e_1_3_2_15_2","volume-title":"Graph Theory","author":"Diestel Reinhard","year":"2012","unstructured":"Reinhard Diestel. 2012. Graph Theory. Springer."},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(97)00121-2"},{"key":"e_1_3_2_19_2","first-page":"463","article-title":"A combinatorial problem in geometry","volume":"2","author":"Erd\u00f6s Paul","year":"1935","unstructured":"Paul Erd\u00f6s and George Szekeres. 1935. A combinatorial problem in geometry. Compositio Mathematica 2 (1935), 463\u2013470.","journal-title":"Compositio Mathematica"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2016.06.004"},{"issue":"4","key":"e_1_3_2_21_2","first-page":"29:1","article-title":"Efficient computation of representative families with applications in parameterized and exact algorithms","volume":"63","author":"Fomin Fedor V.","year":"2016","unstructured":"Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. 2016. Efficient computation of representative families with applications in parameterized and exact algorithms. Journal of the ACM 63, 4 (2016), 29:1\u201329:60.","journal-title":"Journal of the ACM"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1137\/16M1080264"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579200"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.5555\/578533"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009810"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.5555\/647679.732154"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480190177042"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1137\/0210054"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/321850.321852"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/234533.234534"},{"key":"e_1_3_2_31_2","first-page":"1","volume-title":"Proceedings of the 33rd International Symposium on Algorithms and Computation (ISAAC)","volume":"47","author":"Kobayashi Yusuke","year":"2022","unstructured":"Yusuke Kobayashi and Tatsuya Terao. 2022. One-face shortest disjoint paths with a deviation terminal. In Proceedings of the 33rd International Symposium on Algorithms and Computation (ISAAC). Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik, Article 47, 1\u201315."},{"key":"e_1_3_2_32_2","first-page":"169","volume-title":"Proceedings of the 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Lochet William","year":"2021","unstructured":"William Lochet. 2021. A polynomial time algorithm for the \\( k \\) -disjoint shortest paths problem. In Proceedings of the 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 169\u2013178."},{"key":"e_1_3_2_33_2","first-page":"346","volume-title":"Proceedings of 35th ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Mari Mathieu","year":"2024","unstructured":"Mathieu Mari, Anish Mukherjee, Micha\u0142 Pilipczuk, and Piotr Sankowski. 2024. Shortest disjoint paths on a grid. In Proceedings of 35th ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 346\u2013365."},{"key":"e_1_3_2_34_2","doi-asserted-by":"crossref","unstructured":"Dieter Rautenbach and Friedrich Regen. 2009. On packing shortest cycles in graphs. Information Processing Letters 109 14 (2009) 816\u2013821.","DOI":"10.1016\/j.ipl.2009.04.001"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1997.1750"},{"key":"e_1_3_2_36_2","first-page":"1","volume-title":"Proceeding of the 51st International Colloquium on Automata, Languages, and Programming (ICALP)","volume":"122","author":"Schlomberg Niklas","year":"2024","unstructured":"Niklas Schlomberg. 2024. An improved integrality gap for disjoint cycles in planar graphs. In Proceeding of the 51st International Colloquium on Automata, Languages, and Programming (ICALP). Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik, Article 122, 1\u201315."},{"key":"e_1_3_2_37_2","doi-asserted-by":"crossref","first-page":"2069","DOI":"10.1137\/1.9781611977554.ch79","volume-title":"Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Schlomberg Niklas","year":"2023","unstructured":"Niklas Schlomberg, Hanjo Thiele, and Jens Vygen. 2023. Packing cycles in planar and bounded-genus graphs. In Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2069\u20132086."},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(84)90081-7"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3765285","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T15:03:42Z","timestamp":1759849422000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3765285"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,7]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,1,31]]}},"alternative-id":["10.1145\/3765285"],"URL":"https:\/\/doi.org\/10.1145\/3765285","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,7]]},"assertion":[{"value":"2024-10-28","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-08-23","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-10-07","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}