{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:42:50Z","timestamp":1787323370679,"version":"build-2736575974"},"reference-count":30,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/501100006475","name":"Bergens Forskningsstiftelse","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100006475","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["306992"],"award-info":[{"award-number":["306992"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>A key result in the field of kernelization, a subfield of parameterized complexity, states that the classic Disjoint Cycle Packing problem, i.e., finding $k$ vertex disjoint cycles in a given graph $G$, admits no polynomial kernel unless ${\\sf NP} \\subseteq {\\sf coNP} \/ {\\sf poly}$. However, very little is known about this problem beyond the aforementioned kernelization lower bound (within the parameterized complexity framework). In the hope of clarifying the picture and better understanding the types of constraints that separate kernelizable from nonkernelizable variants of Disjoint Cycle Packing, we investigate two relaxations of the problem. The first variant, which we call Almost Disjoint Cycle Packing, introduces a global relaxation parameter $t$. That is, given a graph $G$ and integers $k$ and $t$, the goal is to find at least $k$ distinct cycles such that every vertex of $G$ appears in at most $t$ of the cycles. The second variant, Pairwise Disjoint Cycle Packing, introduces a local relaxation parameter, and we seek at least $k$ distinct cycles such that every two cycles intersect in at most $t$ vertices. While the Pairwise Disjoint Cycle Packing problem admits a polynomial kernel for all $t \\geq 1$, the kernelization complexity of Almost Disjoint Cycle Packing reveals an interesting spectrum of upper and lower bounds. In particular, for $t = \\frac{k}{c}$, where $c$ could be a function of $k$, we obtain a kernel of size $\\mathcal{O}(2^{c^2}k^{7 + c}\\log^3 k)$ whenever $c\\in o(\\sqrt k)$. Thus the kernel size varies from being subexponential when $c\\in o(\\sqrt k)$, to quasi-polynomial when $c\\in o(\\log^{\\ell} k)$, $\\ell \\in \\mathbb{R}_+$, and polynomial when $c\\in \\mathcal{O}(1)$. We complement these results for Almost Disjoint Cycle Packing by showing that the problem does not admit a polynomial kernel whenever $t \\in \\mathcal{O}(k^{\\epsilon})$ for any $0 \\leq \\epsilon &lt; 1$, unless ${\\sf NP} \\subseteq {\\sf coNP} \/ {\\sf poly}$.<\/jats:p>","DOI":"10.1137\/17m1136614","type":"journal-article","created":{"date-parts":[[2018,7,13]],"date-time":"2018-07-13T08:20:31Z","timestamp":1531470031000},"page":"1619-1643","source":"Crossref","is-referenced-by-count":2,"title":["Kernelization of Cycle Packing with Relaxed Disjointness Constraints"],"prefix":"10.1137","volume":"32","author":[{"given":"Akanksha","family":"Agrawal","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2677-4648","authenticated-orcid":true,"given":"Diptapriyo","family":"Majumdar","sequence":"additional","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"}]}],"member":"351","published-online":{"date-parts":[[2018,7,12]]},"reference":[{"key":"atypb1","first-page":"1","author":"Abasi H.","year":"2014","journal-title":"Berlin"},{"key":"atypb2","unstructured":"A. Agrawal, D. Lokshtanov, D. Majumdar, A. E. Mouawad, and S. Saurabh,\n                      Kernelization of cycle packing with relaxed disjointness constraints\n                      , in Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016, pp. 26:1-26:14."},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793251219"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.04.001"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxm037"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.04.039"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh,\n                      Parameterized Algorithms\n                      , Springer-Verlag, Berlin, 2015.","DOI":"10.1007\/978-3-319-21275-3"},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"H. Dell and D. Marx,\n                      Kernelization of packing problems\n                      , in Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, 2012, pp. 68-81.","DOI":"10.1137\/1.9781611973099.6"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1145\/2629620"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"R. Diestel,\n                      Graph Theory\n                      , 4th ed., Grad. Texts in Math 173, Springer-Verlag, Berlin, 2012.","DOI":"10.1007\/978-3-662-53622-3_7"},{"key":"atypb12","unstructured":"R. G. Downey and M. R. Fellows,\n                      Parameterized Complexity\n                      , Springer-Verlag, Berlin, 1997."},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1137\/130927115"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1965-035-8"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"H. Fernau, A. Lo\u0301pez-Ortiz, and J. Romero,\n                      Kernelization algorithms for packing problems allowing overlaps\n                      , in Proceedings of the 12th Annual Conference of Theory and Applications of Models of Computation, 2015, pp. 415-427.","DOI":"10.1007\/978-3-319-17142-5_35"},{"key":"atypb16","unstructured":"J. Flum and M. Grohe,\n                      Parameterized Complexity Theory\n                      , Springer, New York, 2006."},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.06.007"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"A. Gabizon, D. Lokshtanov, and M. Pilipczuk,\n                      Fast algorithms for parameterized problems with relaxed disjointness constraints\n                      , in Proceedings of the 23rd Annual European Symposium on Algorithms, 2015, pp. 545-556.","DOI":"10.1007\/978-3-662-48350-3_46"},{"key":"atypb19","unstructured":"M. Grohe,\n                      Logic, graphs, and algorithms\n                      , in Proceedings of Electronic Colloquium on Computational Complexity, 2007."},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9910-8"},{"key":"atypb21","doi-asserted-by":"crossref","unstructured":"D. Hermelin and X. Wu,\n                      Weak compositions and their applications to polynomial lower bounds for kernelization\n                      , in Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, 2012, pp. 104-113.","DOI":"10.1137\/1.9781611973099.9"},{"key":"atypb22","first-page":"113","author":"Kratsch S.","year":"2014","journal-title":"Bull. Eur. Assoc. Theor. Comput."},{"key":"atypb23","unstructured":"D. Lokshtanov, N. Misra, and S. Saurabh,\n                      Kernelization-preprocessing with a guarantee\n                      , in The Multivariate Algorithmic Revolution and Beyond-Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday, H. L. Bodlaender, R. Downey, F. V. Fomin, D. Marx, eds., 2012, pp. 129-161."},{"key":"atypb24","unstructured":"D. Lokshtanov, F. Panolan, M. S. Ramanujan, and S. Saurabh,\n                      Lossy kernelization\n                      , preprint,https:\/\/arxiv.org\/abs\/1604.04111[CS.DS], 2016."},{"key":"atypb25","doi-asserted-by":"crossref","unstructured":"R. Niedermeier,\n                      Invitation to Fixed-Parameter Algorithms\n                      , Oxford University Press, Oxford, 2006.","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"atypb26","first-page":"907","volume":"10","author":"Ramon J.","year":"2009","journal-title":"J. Mach. Learn. Res."},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80001-6"},{"key":"atypb28","doi-asserted-by":"crossref","unstructured":"J. Romero and A. Lo\u0301pez-Ortiz,\n                      The $\\mathcal{G}$-packing with t-overlap problem\n                      , in Proceedings of the 8th International Workshop on Algorithms and Computation, 2014, pp. 114-124.","DOI":"10.1007\/978-3-319-04657-0_13"},{"key":"atypb29","first-page":"325","author":"Romero J.","year":"2014","journal-title":"New York"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1145\/1721837.1721848"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1136614","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:58:30Z","timestamp":1787320710000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1136614"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":30,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/17M1136614"],"URL":"https:\/\/doi.org\/10.1137\/17m1136614","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}