{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T02:40:21Z","timestamp":1777516821513,"version":"3.51.4"},"reference-count":47,"publisher":"SAGE Publications","issue":"1","license":[{"start":{"date-parts":[[2019,11,14]],"date-time":"2019-11-14T00:00:00Z","timestamp":1573689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Computability"],"published-print":{"date-parts":[[2020,2,26]]},"abstract":"<jats:p>Kernelization\u00a0\u2013 a mathematical key concept for provably effective polynomial-time preprocessing of NP-hard problems\u00a0\u2013 plays a central role in parameterized complexity and has triggered an extensive line of research. This is in part due to a lower bounds framework that allows to exclude polynomial-size kernels under the assumption of [Formula: see text]. In this paper we consider a restricted yet natural variant of kernelization, namely strict kernelization, where one is not allowed to increase the parameter of the reduced instance (the kernel) by more than an additive constant. Building on earlier work of Chen, Flum, and M\u00fcller\u00a0[CiE\u00a02009, Theory\u00a0Comput.\u00a0Syst.\u00a02011], we underline the applicability of their framework by showing that a variety of fixed-parameter tractable problems, including graph problems and Turing machine computation problems, does not admit strict polynomial kernels under the assumption of [Formula: see text], an assumption being weaker than the assumption of [Formula: see text]. Finally, we study an adaption of the framework to a relaxation of the notion of strict kernels, where in the latter one is not allowed to increase the parameter of the reduced instance by more than a constant times the input parameter.<\/jats:p>","DOI":"10.3233\/com-180220","type":"journal-article","created":{"date-parts":[[2019,11,15]],"date-time":"2019-11-15T11:50:40Z","timestamp":1573818640000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":1,"title":["Diminishable parameterized problems and strict polynomial kernelization"],"prefix":"10.1177","volume":"9","author":[{"given":"Henning","family":"Fernau","sequence":"first","affiliation":[{"name":"Fachbereich 4 \u2013 Abteilung Informatikwissenschaften, Universit\u00e4t Trier, Germany."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Till","family":"Fluschnik","sequence":"additional","affiliation":[{"name":"Algorithmics and Computational Complexity, Faculty\u00a0IV, Technische Universit\u00e4t Berlin, Germany."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Danny","family":"Hermelin","sequence":"additional","affiliation":[{"name":"Ben Gurion University of the Negev, Beersheba, Israel."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andreas","family":"Krebs","sequence":"additional","affiliation":[{"name":"Wilhelm-Schickard-Institut f\u00fcr Informatik, Universit\u00e4t T\u00fcbingen, Germany."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hendrik","family":"Molter","sequence":"additional","affiliation":[{"name":"Algorithmics and Computational Complexity, Faculty\u00a0IV, Technische Universit\u00e4t Berlin, Germany."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rolf","family":"Niedermeier","sequence":"additional","affiliation":[{"name":"Algorithmics and Computational Complexity, Faculty\u00a0IV, Technische Universit\u00e4t Berlin, Germany."}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2019,11,14]]},"reference":[{"key":"ref001","doi-asserted-by":"publisher","DOI":"10.1007\/11847250_24"},{"key":"ref002","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210337"},{"key":"ref003","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.07.005"},{"key":"ref004","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2011.19"},{"key":"ref005","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2015.05.013"},{"key":"ref006","doi-asserted-by":"publisher","DOI":"10.1145\/2344422.2344428"},{"key":"ref007","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.04.001"},{"key":"ref008","doi-asserted-by":"publisher","DOI":"10.1137\/0222038"},{"key":"ref009","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(95)00020-8"},{"key":"ref010","doi-asserted-by":"publisher","DOI":"10.1137\/050646354"},{"key":"ref011","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2001.1186"},{"key":"ref012","doi-asserted-by":"crossref","unstructured":"Y.\u00a0Chen, J.\u00a0Flum and M.\u00a0M\u00fcller, Lower bounds for kernelizations and other preprocessing procedures, in: Proceedings of the 5th Conference on Computability in Europe (CiE 2009), Lecture Notes in Computer Science, Vol.\u00a05635, Springer, 2009, pp.\u00a0118\u2013128.","DOI":"10.1007\/978-3-642-03073-4_13"},{"key":"ref013","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-010-9270-y"},{"key":"ref014","unstructured":"J.\u00a0Chv\u00e1talov\u00e1, A.\u00a0Dewdney, N.\u00a0Gibbs and R.\u00a0Korfhage, The bandwidth problem for graphs\u00a0\u2013 a collection of recent results, Technical Report, CS 7502, Department of Computer Science, Southern Methodist University, 1975."},{"key":"ref015","doi-asserted-by":"crossref","unstructured":"M.\u00a0Cygan, F.V.\u00a0Fomin, \u0141.\u00a0Kowalik, D.\u00a0Lokshtanov, D.\u00a0Marx, M.\u00a0Pilipczuk, M.\u00a0Pilipczuk and S.\u00a0Saurabh, Parameterized Algorithms, Springer, 2015.","DOI":"10.1007\/978-3-319-21275-3"},{"key":"ref016","doi-asserted-by":"publisher","DOI":"10.1137\/130947076"},{"key":"ref017","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2012.05.016"},{"key":"ref018","doi-asserted-by":"publisher","DOI":"10.1145\/568522.568523"},{"key":"ref019","doi-asserted-by":"crossref","unstructured":"R.\u00a0Diestel, Graph Theory, 4th edn, Springer, 2010.","DOI":"10.1007\/978-3-642-14279-6"},{"key":"ref020","doi-asserted-by":"crossref","unstructured":"R.G.\u00a0Downey and M.R.\u00a0Fellows, Parameterized Complexity, Monographs in Computer Science, Springer, 1999.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"ref021","doi-asserted-by":"crossref","unstructured":"R.G.\u00a0Downey and M.R.\u00a0Fellows, Fundamentals of Parameterized Complexity, Springer, 2013.","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"ref022","doi-asserted-by":"crossref","unstructured":"R.G.\u00a0Downey, M.R.\u00a0Fellows and U.\u00a0Stege, Parameterized complexity: A framework for systematically confronting computational intractability, in: Proceedings of a DIMACS Workshop on Contemporary Trends in Discrete Mathematics: From DIMACS and DIMATIA to the Future, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol.\u00a049, DIMACS\/AMS, 1997, pp.\u00a049\u201399.","DOI":"10.1090\/dimacs\/049\/04"},{"key":"ref023","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230010302"},{"key":"ref024","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2017.11.001"},{"key":"ref025","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-78825-8_3"},{"key":"ref026","doi-asserted-by":"crossref","unstructured":"H.\u00a0Fernau, T.\u00a0Fluschnik, D.\u00a0Hermelin, A.\u00a0Krebs, H.\u00a0Molter and R.\u00a0Niedermeier, Diminishable parameterized problems and strict polynomial kernelization, in: Proceedings of the 14th Conference on Computability in Europe (CiE 2018), Lecture Notes in Computer Science, Vol.\u00a010936, Springer, 2018, pp.\u00a0161\u2013171.","DOI":"10.1007\/978-3-319-94418-0_17"},{"key":"ref027","unstructured":"H.\u00a0Fernau and D.\u00a0Raible, Alliances in graphs: A complexity-theoretic study, in: Proceedings of the 33rd Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2007), Vol.\u00a0II, Institute of Computer Science AS CR, Prague, 2007, pp.\u00a061\u201370."},{"key":"ref028","unstructured":"J.\u00a0Flum and M.\u00a0Grohe, Parameterized Complexity Theory, Springer, 2006."},{"key":"ref029","doi-asserted-by":"crossref","unstructured":"T.\u00a0Fluschnik, G.B.\u00a0Mertzios and A.\u00a0Nichterlein, Kernelization lower bounds for finding constant-size subgraphs, in: Proceedings of the 14th Conference on Computability in Europe (CiE 2018), Lecture Notes in Computer Science, Vol.\u00a010936, Springer, 2018, pp.\u00a0183\u2013193.","DOI":"10.1007\/978-3-319-94418-0_19"},{"key":"ref030","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.06.007"},{"key":"ref031","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2017.05.017"},{"key":"ref032","doi-asserted-by":"publisher","DOI":"10.1145\/1233481.1233493"},{"issue":"3","key":"ref033","first-page":"702","volume":"71","author":"Hermelin D.","year":"2015","journal-title":"A Completeness Theory for Polynomial (Turing) Kernelization, Algorithmica"},{"key":"ref034","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2012.08.005"},{"key":"ref035","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"issue":"2","key":"ref036","first-page":"191","volume":"28","author":"Karp R.M.","year":"1982","journal-title":"L\u2019Enseignement Math\u00e9matique"},{"key":"ref037","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90234-M"},{"key":"ref038","unstructured":"S.\u00a0Kratsch, Recent developments in kernelization: A survey, Bulletin of the EATCS 113 (2014)."},{"key":"ref039","first-page":"157","volume":"48","author":"Kristiansen P.","year":"2004","journal-title":"Journal of Combinatorial Mathematics and Combinatorial Computing"},{"key":"ref040","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(02)00227-2"},{"key":"ref041","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2016.06.044"},{"key":"ref042","first-page":"41","author":"Lokshtanov D.","year":"2011","journal-title":"Bulletin of the EATCS"},{"key":"ref043","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055456"},{"key":"ref044","doi-asserted-by":"crossref","unstructured":"R.\u00a0Niedermeier, Invitation to Fixed-Parameter Algorithms, Oxford University Press, 2006.","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"ref045","doi-asserted-by":"publisher","DOI":"10.1007\/s11590-011-0311-5"},{"key":"ref046","unstructured":"M.\u00a0Sorge and M.\u00a0Weller, The graph parameter hierarchy, 2018, https:\/\/manyu.pro\/assets\/parameter-hierarchy.pdf."},{"key":"ref047","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-55911-7_47"}],"container-title":["Computability"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/COM-180220","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.3233\/COM-180220","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/COM-180220","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T16:00:11Z","timestamp":1777392011000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/full\/10.3233\/COM-180220"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,14]]},"references-count":47,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,2,26]]}},"alternative-id":["10.3233\/COM-180220"],"URL":"https:\/\/doi.org\/10.3233\/com-180220","relation":{},"ISSN":["2211-3568","2211-3576"],"issn-type":[{"value":"2211-3568","type":"print"},{"value":"2211-3576","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,11,14]]}}}