{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:35:14Z","timestamp":1750221314923,"version":"3.41.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2017,7,31]],"date-time":"2017-07-31T00:00:00Z","timestamp":1501459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001711","name":"SNSF","doi-asserted-by":"crossref","award":["200021_159697\/1"],"award-info":[{"award-number":["200021_159697\/1"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"crossref"}]},{"name":"ERC Starting","award":["NEWNET 279352"],"award-info":[{"award-number":["NEWNET 279352"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2017,7,31]]},"abstract":"<jats:p>Kernelization is a strong and widely applied technique in parameterized complexity. In a nutshell, a kernelization algorithm for a parameterized problem transforms in polynomial time a given instance of the problem into an equivalent instance whose size depends solely on the parameter. Recent years have seen major advances in the study of both upper and lower bound techniques for kernelization, and by now this area has become one of the major research threads in parameterized complexity.<\/jats:p>\n          <jats:p>\n            In this article, we consider kernelization for problems on\n            <jats:italic>d<\/jats:italic>\n            -degenerate graphs, that is, graphs such that any subgraph contains a vertex of degree at most\n            <jats:italic>d<\/jats:italic>\n            . This graph class generalizes many classes of graphs for which effective kernelization is known to exist, for example, planar graphs,\n            <jats:italic>H<\/jats:italic>\n            -minor free graphs, and\n            <jats:italic>H<\/jats:italic>\n            -topological-minor free graphs. We show that for several natural problems on\n            <jats:italic>d<\/jats:italic>\n            -degenerate graphs the best-known kernelization upper bounds are essentially tight. In particular, using intricate constructions of weak compositions, we prove that unless coNP \u2286 NP\/poly:\n          <\/jats:p>\n          <jats:p>\n            \u2022 D\n            <jats:sc>ominating<\/jats:sc>\n            S\n            <jats:sc>et<\/jats:sc>\n            has no kernels of size\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>\n              (\n              <jats:italic>d<\/jats:italic>\n              \u22121)(\n              <jats:italic>d<\/jats:italic>\n              \u22123)\u2212\u03b5\n            <\/jats:sup>\n            ) for any \u03b5 &gt; 0. The current best upper bound is\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>(d+1)<\/jats:sup>\n            <jats:sup>2<\/jats:sup>\n            ).\n          <\/jats:p>\n          <jats:p>\n            \u2022 I\n            <jats:sc>ndependent<\/jats:sc>\n            D\n            <jats:sc>ominating<\/jats:sc>\n            S\n            <jats:sc>et<\/jats:sc>\n            has no kernels of size\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>\n              <jats:italic>d<\/jats:italic>\n              \u22124\u2212\u03b5\n            <\/jats:sup>\n            ) for any \u03b5 &gt; 0. The current best upper bound is\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>\n              <jats:italic>d<\/jats:italic>\n              +1\n            <\/jats:sup>\n            ).\n          <\/jats:p>\n          <jats:p>\n            \u2022 I\n            <jats:sc>nduced<\/jats:sc>\n            M\n            <jats:sc>atching<\/jats:sc>\n            has no kernels of size\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>\n              <jats:italic>d<\/jats:italic>\n              \u22123\u2212\u03b5\n            <\/jats:sup>\n            ) for any \u03b5 &gt; 0. The current best upper bound is\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>\n              k\n              <jats:sup>d<\/jats:sup>\n            <\/jats:italic>\n            ).\n          <\/jats:p>\n          <jats:p>\n            To the best of our knowledge, D\n            <jats:sc>ominating<\/jats:sc>\n            S\n            <jats:sup>et<\/jats:sup>\n            is the the first problem where a lower bound with superlinear dependence on\n            <jats:italic>d<\/jats:italic>\n            (in the exponent) can be proved.\n          <\/jats:p>\n          <jats:p>\n            In the last section of the article, we also give simple kernels for C\n            <jats:sc>onnected<\/jats:sc>\n            V\n            <jats:sc>ertex<\/jats:sc>\n            C\n            <jats:sc>over<\/jats:sc>\n            and C\n            <jats:sc>apacitated<\/jats:sc>\n            V\n            <jats:sc>ertex<\/jats:sc>\n            C\n            <jats:sc>over<\/jats:sc>\n            of size\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>\n              k\n              <jats:sup>d<\/jats:sup>\n            <\/jats:italic>\n            ) and\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>\n              <jats:italic>d<\/jats:italic>\n              +1\n            <\/jats:sup>\n            ), respectively. We show that the latter problem has no kernels of size\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>\n              <jats:italic>d<\/jats:italic>\n              \u2212\u03b5\n            <\/jats:sup>\n            ) unless coNP \u2286 NP\/poly by a simple reduction from\n            <jats:italic>d<\/jats:italic>\n            -E\n            <jats:sc>xact<\/jats:sc>\n            S\n            <jats:sc>et<\/jats:sc>\n            C\n            <jats:sc>over<\/jats:sc>\n            (the same lower bound for C\n            <jats:sc>onnected<\/jats:sc>\n            V\n            <jats:sc>ertex<\/jats:sc>\n            C\n            <jats:sc>over<\/jats:sc>\n            on\n            <jats:italic>d<\/jats:italic>\n            -degenerate graphs is already known).\n          <\/jats:p>","DOI":"10.1145\/3108239","type":"journal-article","created":{"date-parts":[[2017,8,10]],"date-time":"2017-08-10T12:12:29Z","timestamp":1502367149000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Tight Kernel Bounds for Problems on Graphs with Small Degeneracy"],"prefix":"10.1145","volume":"13","author":[{"given":"Marek","family":"Cygan","sequence":"first","affiliation":[{"name":"Institute for Informatics, Warsaw, Poland"}]},{"given":"Fabrizio","family":"Grandoni","sequence":"additional","affiliation":[{"name":"Dalle Molle Institute (IDSIA), Manno, Switzerland"}]},{"given":"Danny","family":"Hermelin","sequence":"additional","affiliation":[{"name":"Ben-Gurion University, Beer-Sheva, Israel"}]}],"member":"320","published-online":{"date-parts":[[2017,8,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990309"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.04.001"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1747597.1747997"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/120880240"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.04.039"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(95)00020-8"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-010-9270-y"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2012.05.016"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095122"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629620"},{"key":"e_1_2_1_11_1","volume-title":"Graph Theory","author":"Diestel Reinhard","unstructured":"Reinhard Diestel . 2005. Graph Theory ( 3 rd ed.). Springer-Verlag . Reinhard Diestel. 2005. Graph Theory (3rd ed.). Springer-Verlag.","edition":"3"},{"key":"e_1_2_1_12_1","article-title":"Kernelization lower bounds through colors and IDs","volume":"11","author":"Dom Michael","year":"2014","unstructured":"Michael Dom , Daniel Lokshtanov , and Saket Saurabh . 2014 . Kernelization lower bounds through colors and IDs . ACM Trans. Algor. 11 , 2 (2014), 13:1--13:20. Michael Dom, Daniel Lokshtanov, and Saket Saurabh. 2014. Kernelization lower bounds through colors and IDs. ACM Trans. Algor. 11, 2 (2014), 13:1--13:20.","journal-title":"ACM Trans. Algor."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science (STACS\u201916)","author":"Drange P\u00e5l Gr\u00f8n\u00e5s","year":"2016","unstructured":"P\u00e5l Gr\u00f8n\u00e5s Drange , Markus Sortland Dregi , Fedor V. Fomin , Stephan Kreutzer , Daniel Lokshtanov , Marcin Pilipczuk , Michal Pilipczuk , Felix Reidl , Fernando S\u00e1nchez Villaamil , Saket Saurabh , Sebastian Siebertz , and Somnath Sikdar . 2016 . Kernelization and sparseness: The case of dominating set . In Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science (STACS\u201916) . 31:1--31:14. P\u00e5l Gr\u00f8n\u00e5s Drange, Markus Sortland Dregi, Fedor V. Fomin, Stephan Kreutzer, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Felix Reidl, Fernando S\u00e1nchez Villaamil, Saket Saurabh, Sebastian Siebertz, and Somnath Sikdar. 2016. Kernelization and sparseness: The case of dominating set. In Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science (STACS\u201916). 31:1--31:14."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2010.08.026"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39890-5_1"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/11847250_25"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.09.065"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075.43"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.7"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.06.007"},{"key":"e_1_2_1_22_1","volume-title":"Johnson","author":"Garey Michael R.","year":"1979","unstructured":"Michael R. Garey and David S . Johnson . 1979 . Computers and Intractability: A Guide to the Theory of NP-completeness. W. H. Freeman . Michael R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-completeness. W. H. Freeman."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1233481.1233493"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-73420-8_34"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/060668092"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9910-8"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.9"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.09.001"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_2_1_30_1","article-title":"Co-nondeterminism in composi0tions: A kernelization lower bound for a ramsey-type problem","volume":"10","author":"Kratsch Stefan","year":"2014","unstructured":"Stefan Kratsch . 2014 . Co-nondeterminism in composi0tions: A kernelization lower bound for a ramsey-type problem . ACM Trans. Algor. 10 , 4 (2014), 19:1--19:16. Stefan Kratsch. 2014. Co-nondeterminism in composi0tions: A kernelization lower bound for a ramsey-type problem. ACM Trans. Algor. 10, 4 (2014), 19:1--19:16.","journal-title":"ACM Trans. Algor."},{"key":"e_1_2_1_31_1","volume-title":"Linear kernels on graphs excluding topological minors. CoRR abs\/1201.2780","author":"Langer Alexander","year":"2012","unstructured":"Alexander Langer , Felix Reidl , Peter Rossmanith , and Somnath Sikdar . 2012. Linear kernels on graphs excluding topological minors. CoRR abs\/1201.2780 ( 2012 ). Alexander Langer, Felix Reidl, Peter Rossmanith, and Somnath Sikdar. 2012. Linear kernels on graphs excluding topological minors. CoRR abs\/1201.2780 (2012)."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580444"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2390176.2390187"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3108239","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3108239","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:13:43Z","timestamp":1750212823000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3108239"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,7,31]]},"references-count":33,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,7,31]]}},"alternative-id":["10.1145\/3108239"],"URL":"https:\/\/doi.org\/10.1145\/3108239","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2017,7,31]]},"assertion":[{"value":"2014-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-08-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}