{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,26]],"date-time":"2026-10-26T07:34:23Z","timestamp":1793000063095,"version":"4.5.0"},"reference-count":78,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2026,10,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>In this paper we propose a new framework for analyzing the performance of preprocessing algorithms. Our framework builds on the notion of kernelization from parameterized complexity. However, as opposed to the original notion of kernelization, our definitions combine well with approximation algorithms and heuristics. The key new definition is that of a polynomial size [Formula: see text]-approximate kernel. Loosely speaking, a polynomial size [Formula: see text]-approximate kernel is a polynomial-time preprocessing algorithm that takes as input an instance [Formula: see text] to a parameterized problem, and outputs another instance [Formula: see text] to the same problem, such that [Formula: see text]. Additionally, for every [Formula: see text], a [Formula: see text]-approximate solution [Formula: see text] to the preprocessed instance [Formula: see text] can be turned in polynomial time into a [Formula: see text]-approximate solution [Formula: see text] to the original instance [Formula: see text]. Our main technical contributions are [Formula: see text]-approximate kernels of polynomial size for three problems, namely, Connected Vertex Cover, Disjoint Cycle Packing, and Disjoint Factors. These problems are known not to admit any polynomial size kernels unless NP [Formula: see text] [Formula: see text]. Our approximate kernels simultaneously beat both the lower bounds on the (normal) kernel size and the hardness of approximation lower bounds for all three problems. On the negative side we prove that Longest Path parameterized by the length of the path and Set Cover parameterized by the universe size do not admit even an [Formula: see text]-approximate kernel of polynomial size, for any [Formula: see text], unless NP [Formula: see text] [Formula: see text]. In order to prove this lower bound, we need to combine in a nontrivial way the techniques used for showing kernelization lower bounds with the methods for showing hardness of approximation.<\/jats:p>","DOI":"10.1137\/25m179628x","type":"journal-article","created":{"date-parts":[[2026,10,26]],"date-time":"2026-10-26T07:00:36Z","timestamp":1792998036000},"page":"1032-1097","source":"Crossref","is-referenced-by-count":0,"title":["Lossy Kernelization"],"prefix":"10.1137","volume":"55","author":[{"given":"Daniel","family":"Lokshtanov","sequence":"first","affiliation":[{"name":"University of California Santa Barbara, Santa Barbara, CA 93106 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6213-8687","authenticated-orcid":true,"given":"Fahad","family":"Panolan","sequence":"additional","affiliation":[{"name":"School of Computer Science, University of Leeds, Leeds, UK."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"M. S.","family":"Ramanujan","sequence":"additional","affiliation":[{"name":"University of Warwick, Coventry, UK."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[{"name":"The Institute of Mathematical Sciences, HBNI, Chennai, India, and University of Bergen, Bergen, Norway."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2026,10,26]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.09.002"},{"key":"ref2","first-page":"36:1","volume-title":"43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2023, December 18-20, 2023, IIIT Hyderabad, Telangana, India, LIPIcs 284","author":"Agrawal A.","year":"2023"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210337"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1137\/080729256"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90072-H"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1145\/2775105"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-023-10129-9"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.04.001"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1137\/120880240"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.04.039"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795281086"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1613\/jair.4285"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1145\/2432622.2432628"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2008.07.003"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1287\/moor.4.3.233"},{"key":"ref17","volume-title":"Introduction to Algorithms","author":"Cormen T. H.","year":"2001","edition":"2"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3"},{"key":"ref19","doi-asserted-by":"crossref","unstructured":"H. Dell and D. Marx, Kernelization of packing problems, in Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, January 17-19, 2012, Kyoto, Japan, 2012, pp. 68\u201381.","DOI":"10.1137\/1.9781611973099.6"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1145\/2629620"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.12.023"},{"key":"ref22","series-title":"Grad. Texts in Math. 173","volume-title":"Graph Theory","author":"Diestel R.","year":"2005","edition":"3"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704443057"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2005.162.439"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1145\/2650261"},{"key":"ref26","volume-title":"Parameterized Complexity","author":"Downey R. G.","year":"2012"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230010302"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1137\/130927115"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2019.05.001"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1137\/18M1172508"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-15914-5_15"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1965-035-8"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2001.1183"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2006.07.009"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1145\/2898352"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2017.11.001"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.10.035"},{"key":"ref38","first-page":"49:1","volume-title":"31st Annual European Symposium on Algorithms, ESA 2023, September 4\u20136, 2023, Amsterdam, The Netherlands, LIPIcs 274","author":"Fomin F. V.","year":"2023"},{"key":"ref39","doi-asserted-by":"crossref","unstructured":"F. V. Fomin, D. Lokshtanov, N. Misra, and S. Saurabh, Planar \\(\\mathcal{F}\\)-deletion: Approximation, kernelization and optimal FPT algorithms, in Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2012, pp. 470\u2013479, https:\/\/doi.org\/10.1109\/FOCS.2012.62.","DOI":"10.1109\/FOCS.2012.62"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.06.007"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-009-9349-5"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1145\/3029051"},{"key":"ref43","first-page":"53:1","volume-title":"27th Annual European Symposium on Algorithms, ESA 2019, September 9\u201311, 2019, Munich\/Garching, Germany, LIPIcs 144","author":"Grandoni F.","year":"2019"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1145\/3470869"},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.01.056"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-1309-3"},{"key":"ref47","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9910-8"},{"key":"ref48","doi-asserted-by":"crossref","unstructured":"D. Hermelin and X. Wu, Weak compositions and their applications to polynomial lower bounds for kernelization, in Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, January 17\u201319, 2012, Kyoto, Japan, 2012, pp. 104\u2013113.","DOI":"10.1137\/1.9781611973099.9"},{"key":"ref49","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2025.103720"},{"key":"ref50","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"ref51","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"ref52","doi-asserted-by":"publisher","DOI":"10.1137\/22M152058X"},{"key":"ref53","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523689"},{"key":"ref54","doi-asserted-by":"crossref","unstructured":"S. Khot, On the power of unique 2-prover 1-round games, in Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19\u201321, 2002, Qu\u00e9bec, Canada, 2002, pp. 767\u2013775.","DOI":"10.1145\/509907.510017"},{"key":"ref55","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.06.019"},{"key":"ref56","volume":"113","author":"Kratsch S.","year":"2014","journal-title":"Bulletin of the EATCS"},{"key":"ref57","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-017-9837-y"},{"key":"ref58","first-page":"23:1","volume-title":"36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2016, December 13-15, 2016, LIPIcs 65","author":"Krithika R.","year":"2016"},{"key":"ref59","unstructured":"D. Lokshtanov, Parameterized Integer Quadratic Programming: Variables and Coefficients, preprint, arXiv:1511.00310, 2015."},{"key":"ref60","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-30891-8_10"},{"key":"ref61","unstructured":"P. Manurangsi, A note on max k-vertex cover: Faster FPT-as, smaller approximate kernel and improved approximation, in Proceedings of the 2nd Symposium on Simplicity in Algorithms (SOSA), OASIcs, Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik 69, 2019, pp. 15:1\u201315:20, https:\/\/doi.org\/10.4230\/OASIcs.SOSA.2019.15."},{"key":"ref62","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxm048"},{"key":"ref63","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-018-0431-8"},{"key":"ref64","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2015.v011a007"},{"key":"ref65","volume":"14","author":"Nelson J.","year":"2007","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"ref66","doi-asserted-by":"publisher","DOI":"10.1287\/moor.18.1.1"},{"key":"ref67","doi-asserted-by":"publisher","DOI":"10.1007\/BF01202286"},{"key":"ref68","doi-asserted-by":"publisher","DOI":"10.1145\/1159892.1159898"},{"key":"ref69","first-page":"77:1","volume-title":"27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich\/Garching, Germany, LIPIcs 144","author":"Ramanujan M. S.","year":"2019"},{"key":"ref70","series-title":"Leibniz International Proceedings in Informatics (LIPIcs) 204","first-page":"78:1","volume-title":"29th Annual European Symposium on Algorithms (ESA 2021)","author":"Ramanujan M. S.","year":"2021"},{"key":"ref71","doi-asserted-by":"crossref","unstructured":"M. R. Salavatipour and J. Verstra\u00ebte,\n                      Disjoint cycles: Integrality gap, hardness, and approximation\n                      , in Proceedings of the Integer Programming and Combinatorial Optimization, 11th International IPCO Conference, Berlin, Germany, June 8\u201310, 2005, pp. 51\u201365.","DOI":"10.1007\/11496915_5"},{"key":"ref72","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(82)90022-9"},{"key":"ref73","unstructured":"R. Sharma and M. W\u0142odarczyk, Protrusion decompositions revisited: Uniform lossy kernels for reducing treewidth and linear kernels for hitting disconnected minors, in Proceedings of the 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026), Leibniz International Proceedings in Informatics (LIPIcs) 364, Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, 2026, pp. 78:1\u201378:20, https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2026.78, https:\/\/arxiv.org\/abs\/2601.08424."},{"key":"ref74","volume-title":"Introduction to the Theory of Computation","author":"Sipser M.","year":"2012"},{"key":"ref75","doi-asserted-by":"crossref","unstructured":"L. Trevisan, Non-approximability results for optimization problems on bounded degree instances, in Proceedings on 33rd Annual ACM Symposium on Theory of Computing, July 6\u20138, 2001, Heraklion, Crete, Greece, 2001, pp. 453\u2013461, https:\/\/doi.org\/10.1145\/380752.380839.","DOI":"10.1145\/380752.380839"},{"key":"ref76","doi-asserted-by":"publisher","DOI":"10.1002\/net.21985"},{"key":"ref77","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511921735"},{"key":"ref78","doi-asserted-by":"crossref","unstructured":"Y. Yang and J. Guo,\n                      Possible winner problems on partial tournaments: A parameterized study\n                      , in Proceedings of the\u00a0Algorithmic Decision Theory - Third International Conference, ADT 2013, Bruxelles, Belgium, November 12\u201314, 2013, pp. 425\u2013439.","DOI":"10.1007\/978-3-642-41575-3_33"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/25M179628X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,10,26]],"date-time":"2026-10-26T07:00:43Z","timestamp":1792998043000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/25M179628X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,10,26]]},"references-count":78,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2026,10,31]]}},"alternative-id":["10.1137\/25M179628X"],"URL":"https:\/\/doi.org\/10.1137\/25m179628x","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,10,26]]}}}