{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,2]],"date-time":"2026-02-02T20:31:50Z","timestamp":1770064310112,"version":"3.49.0"},"reference-count":65,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2023,3,6]],"date-time":"2023-03-06T00:00:00Z","timestamp":1678060800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"European Research Council (ERC)"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>In parameterized complexity, it is well-known that a parameterized problem is fixed-parameter tractable if and only if it has a kernel\u2014an instance equivalent to the input instance, whose size is just a function of the parameter. The size of the kernel can be exponential or worse, resulting in a quest for fixed-parameter tractable problems with polynomial-sized kernels. The developments in machinery (showing lower bounds for the sizes of the kernels) have led researchers to question what are the asymptotically optimum sizes for the kernels of fixed-parameter tractable problems. In this article, we surveyed a tool called expansion lemma that helps in reducing the size of the kernel. Its early origin was in the form of crown decomposition, i.e., to obtain the linear kernel for the Vertex Cover problem; the specific lemma was identified as the tool behind the optimal O(k2) kernel for the undirected feedback vertex set problem. Since then, several variations and extensions of the tool have been discovered. We surveyed them along with their applications in this article.<\/jats:p>","DOI":"10.3390\/a16030144","type":"journal-article","created":{"date-parts":[[2023,3,7]],"date-time":"2023-03-07T01:43:35Z","timestamp":1678153415000},"page":"144","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Expansion Lemma\u2014Variations and Applications to Polynomial-Time Preprocessing"],"prefix":"10.3390","volume":"16","author":[{"given":"Ashwin","family":"Jacob","sequence":"first","affiliation":[{"name":"Department of Computer Science, Ben-Gurion University of the Negev, Beersheva 8410501, Israel"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2677-4648","authenticated-orcid":false,"given":"Diptapriyo","family":"Majumdar","sequence":"additional","affiliation":[{"name":"Indraprastha Institute of Information Technology Delhi, New Delhi 110020, India"}]},{"given":"Venkatesh","family":"Raman","sequence":"additional","affiliation":[{"name":"The Institute of Mathematical Sciences, HBNI, Chennai 600113, India"}]}],"member":"1968","published-online":{"date-parts":[[2023,3,6]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., and Saurabh, S. (2015). Parameterized Algorithms, Springer.","DOI":"10.1007\/978-3-319-21275-3"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1016\/j.jcss.2009.04.001","article-title":"On problems without polynomial kernels","volume":"75","author":"Bodlaender","year":"2009","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2650261","article-title":"Kernelization lower bounds through colors and IDs","volume":"11","author":"Dom","year":"2014","journal-title":"ACM Trans. Algorithms (TALG)"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2629620","article-title":"Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses","volume":"61","author":"Dell","year":"2014","journal-title":"J. ACM (JACM)"},{"key":"ref_5","unstructured":"Chor, B., Fellows, M., and Juedes, D. (2004). Proceedings of the International Workshop on Graph-Theoretic Concepts in Computer Science, Springer."},{"key":"ref_6","first-page":"1","article-title":"A 4k2 kernel for feedback vertex set","volume":"6","year":"2010","journal-title":"ACM Trans. Algorithms"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Niedermeier, R. (2006). Invitation to Fixed-Parameter Algorithms, Oxford University Press.","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1145\/1233481.1233493","article-title":"Invitation to data reduction and problem kernelization","volume":"38","author":"Guo","year":"2007","journal-title":"SIGACT News"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Downey, R.G., and Fellows, M.R. (2013). Fundamentals of Parameterized Complexity, Springer. Texts in Computer Science.","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"ref_10","unstructured":"Flum, J., and Grohe, M. (2006). Parameterized Complexity Theory, Springer."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., and Zehavi, M. (2019). Kernelization\u2014Theory of Parameterized Preprocessing, Cambridge University Press.","DOI":"10.1017\/9781107415157"},{"key":"ref_12","unstructured":"Diestel, R. (2012). Graph Theory, Springer. [4th ed.]. Graduate Texts in Mathematics."},{"key":"ref_13","first-page":"26","article-title":"On Representatives of Subsets","volume":"S1\u2013S10","author":"Hall","year":"1987","journal-title":"J. Lond. Math. Soc."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","article-title":"Paths, Trees, and Flowers","volume":"17","author":"Edmonds","year":"1965","journal-title":"Can. J. Math."},{"key":"ref_15","unstructured":"Lovasz, L., and Plumber, M.D. (2000). Matching Theory, AMS Chelsea Publishing, American Mathematical Society."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/0095-8956(84)90013-3","article-title":"Graph minors. III. Planar tree-width","volume":"36","author":"Robertson","year":"1984","journal-title":"J. Comb. Theory Ser. B"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","article-title":"Graph Minors. II. Algorithmic Aspects of Tree-Width","volume":"7","author":"Robertson","year":"1986","journal-title":"J. Algorithms"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1016\/0095-8956(90)90120-O","article-title":"Graph minors. IV. Tree-width and well-quasi-ordering","volume":"48","author":"Robertson","year":"1990","journal-title":"J. Comb. Theory Ser. B"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"152","DOI":"10.1016\/j.tcs.2019.04.018","article-title":"Kernels for packing and covering problems","volume":"790","author":"Chen","year":"2019","journal-title":"Theor. Comput. Sci."},{"key":"ref_20","unstructured":"Fellows, M.R. (2003). Proceedings of the International Workshop on Graph-Theoretic Concepts in Computer Science, Springer."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1137\/0202019","article-title":"An n^5\/2 algorithm for maximum matchings in bipartite graphs","volume":"2","author":"Hopcroft","year":"1973","journal-title":"SIAM J. Comput."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"1089","DOI":"10.1016\/j.ipl.2011.09.003","article-title":"A kernel of order 2k \u2212 c log k for vertex cover","volume":"111","author":"Lampis","year":"2011","journal-title":"Inf. Process. Lett."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1016\/j.tcs.2018.05.004","article-title":"A 2k-kernelization algorithm for Vertex Cover based on Crown Decomposition","volume":"739","author":"Li","year":"2018","journal-title":"Theor. Comput. Sci."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1016\/j.tcs.2021.03.035","article-title":"A (2 + \u03f5)k-vertex kernel for the dual coloring problem","volume":"868","author":"Li","year":"2021","journal-title":"Theor. Comput. Sci."},{"key":"ref_25","unstructured":"Lokshtanov, D. (2009). New Methods in Parameterized Algorithms and Complexity, University of Bergen."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"1307","DOI":"10.1007\/s00224-020-10014-9","article-title":"Fixed-parameter tractability of (n \u2212 k) list coloring","volume":"64","author":"Banik","year":"2020","journal-title":"Theory Comput. Syst."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/j.tcs.2012.09.006","article-title":"Kernel bounds for path and cycle problems","volume":"511","author":"Bodlaender","year":"2013","journal-title":"Theor. Comput. Sci."},{"key":"ref_28","unstructured":"Fellows, M., Heggernes, P., Rosamond, F., Sloper, C., and Telle, J.A. (2004). Proceedings of the International Workshop on Graph-Theoretic Concepts in Computer Science, Springer."},{"key":"ref_29","first-page":"308","article-title":"Reducing to independent set structure: The case of k-internal spanning tree","volume":"12","author":"Prieto","year":"2005","journal-title":"Nord. J. Comput."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"292","DOI":"10.1016\/j.dam.2007.03.026","article-title":"Crown reductions for the minimum weighted vertex cover problem","volume":"156","year":"2008","journal-title":"Discret. Appl. Math."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"524","DOI":"10.1016\/j.jcss.2009.09.002","article-title":"A kernelization algorithm for d-hitting set","volume":"76","year":"2010","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"621","DOI":"10.1016\/j.ipl.2010.04.020","article-title":"An improved kernelization algorithm for r-Set Packing","volume":"110","year":"2010","journal-title":"Inf. Process. Lett."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1016\/j.ipl.2009.12.002","article-title":"An improved kernelization for P2-packing","volume":"110","author":"Wang","year":"2010","journal-title":"Inf. Process. Lett."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Gopal, T.V., J\u00e4ger, G., and Steila, S. (2017, January 20\u201322). Kernelization and Parameterized Algorithms for 3-Path Vertex Cover. Proceedings of the Theory and Applications of Models of Computation\u201414th Annual Conference, TAMC 2017, Bern, Switzerland. Lecture Notes in Computer Science.","DOI":"10.1007\/978-3-319-55911-7"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1007\/BF02066678","article-title":"Maximum-minimum S\u00e4tze und verallgemeinerte Faktoren von Graphen","volume":"12","author":"Gallai","year":"1961","journal-title":"Acta Math. Hung."},{"key":"ref_36","unstructured":"Chatzigiannakis, I., Indyk, P., Kuhn, F., and Muscholl, A. (2017, January 10\u201314). Linear-Time Kernelization for Feedback Vertex Set. Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, Warsaw, Poland. LIPIcs."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"13:1","DOI":"10.1145\/3293466","article-title":"Subquadratic Kernels for Implicit 3-Hitting Set and 3-Set Packing Problems","volume":"15","author":"Fomin","year":"2019","journal-title":"ACM Trans. Algorithms"},{"key":"ref_38","unstructured":"Rossmanith, P., Heggernes, P., and Katoen, J. (2019, January 26\u201330). Faster FPT Algorithm for 5-Path Vertex Cover. Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, Aachen, Germany. LIPIcs."},{"key":"ref_39","unstructured":"Cerven\u00fd, R., Choudhary, P., and Such\u00fd, O. (2021). On Kernels for d-Path Vertex Cover. arXiv."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"1910","DOI":"10.1007\/s00224-018-9858-1","article-title":"Polynomial Kernels for Vertex Cover Parameterized by Small Degree Modulators","volume":"62","author":"Majumdar","year":"2018","journal-title":"Theory Comput. Syst."},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Thilikos, D.M. (2010, January 28\u201330). A Quartic Kernel for Pathwidth-One Vertex Deletion. Proceedings of the Graph Theoretic Concepts in Computer Science\u201436th International Workshop, WG 2010, Zar\u00f3s, Crete, Greece. Lecture Notes in Computer Science.","DOI":"10.1007\/978-3-642-16926-7"},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1007\/s00453-011-9578-2","article-title":"An Improved FPT Algorithm and a Quadratic Kernel for Pathwidth One Vertex Deletion","volume":"64","author":"Cygan","year":"2012","journal-title":"Algorithmica"},{"key":"ref_43","unstructured":"Husfeldt, T., and Kanj, I.A. (2015, January 16\u201318). A Polynomial Kernel for Block Graph Deletion. Proceedings of the 10th International Symposium on Parameterized and Exact Computation, IPEC 2015, Patras, Greece. LIPIcs."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/978-3-662-49529-2_1","article-title":"A Faster FPT Algorithm and a Smaller Kernel for Block Graph Vertex Deletion","volume":"Volume 9644","author":"Kranakis","year":"2016","journal-title":"Proceedings of the LATIN 2016: Theoretical Informatics\u201412th Latin American Symposium"},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"2258","DOI":"10.1137\/17M112035X","article-title":"Approximation and Kernelization for Chordal Vertex Deletion","volume":"32","author":"Jansen","year":"2018","journal-title":"SIAM J. Discret. Math."},{"key":"ref_46","first-page":"1","article-title":"Feedback vertex set inspired kernel for chordal vertex deletion","volume":"15","author":"Agrawal","year":"2018","journal-title":"ACM Trans. Algorithms (TALG)"},{"key":"ref_47","first-page":"172","article-title":"Parameterized Algorithms for Even Cycle Transversal","volume":"Volume 7551","author":"Golumbic","year":"2012","journal-title":"Proceedings of the Graph-Theoretic Concepts in Computer Science\u201438th International Workshop, WG 2012"},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1016\/j.disopt.2017.02.002","article-title":"Polynomial kernels for deletion to classes of acyclic digraphs","volume":"25","author":"Mnich","year":"2017","journal-title":"Discret. Optim."},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1016\/j.jcss.2017.07.008","article-title":"Kernels for deletion to classes of acyclic digraphs","volume":"92","author":"Agrawal","year":"2018","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/j.tcs.2012.02.012","article-title":"On Parameterized Independent Feedback Vertex Set","volume":"461","author":"Misra","year":"2012","journal-title":"Theor. Comput. Sci."},{"key":"ref_51","doi-asserted-by":"crossref","first-page":"4570","DOI":"10.1016\/j.tcs.2011.04.039","article-title":"Kernel bounds for disjoint cycles and disjoint paths","volume":"412","author":"Bodlaender","year":"2011","journal-title":"Theor. Comput. Sci."},{"key":"ref_52","doi-asserted-by":"crossref","first-page":"1619","DOI":"10.1137\/17M1136614","article-title":"Kernelization of Cycle Packing with Relaxed Disjointness Constraints","volume":"32","author":"Agrawal","year":"2018","journal-title":"SIAM J. Discret. Math."},{"key":"ref_53","doi-asserted-by":"crossref","unstructured":"Bansal, N., and Nagarajan, V. (2023, January 22\u201325). Kernelization for Graph Packing Problems via Rainbow Matching. Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy.","DOI":"10.1137\/1.9781611977554"},{"key":"ref_54","unstructured":"Lokshtanov, D., and Saurabh, S. (2009). Proceedings of the International Workshop on Parameterized and Exact Computation, Springer."},{"key":"ref_55","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.jcss.2012.03.004","article-title":"A linear vertex kernel for maximum internal spanning tree","volume":"79","author":"Fomin","year":"2013","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_56","unstructured":"Kumar, M., and Lokshtanov, D. (2016, January 24\u201326). A 2lk Kernel for l-Component Order Connectivity. Proceedings of the 11th International Symposium on Parameterized and Exact Computation, IPEC 2016, Aarhus, Denmark."},{"key":"ref_57","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1016\/j.jcss.2017.04.004","article-title":"Linear kernels for separating a graph into components of bounded size","volume":"88","author":"Xiao","year":"2017","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_58","first-page":"5:1","article-title":"Packing Arc-Disjoint 4-Cycles in Oriented Graphs","volume":"Volume 250","author":"Dawar","year":"2022","journal-title":"Proceedings of the 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2022, IIT Madras"},{"key":"ref_59","first-page":"67:1","article-title":"A 7\/3-Approximation for Feedback Vertex Sets in Tournaments","volume":"Volume 57","author":"Sankowski","year":"2016","journal-title":"Proceedings of the 24th Annual European Symposium on Algorithms, ESA 2016"},{"key":"ref_60","first-page":"26:1","article-title":"Balanced Crown Decomposition for Connectivity Constraints","volume":"Volume 204","author":"Mutzel","year":"2021","journal-title":"Proceedings of the 29th Annual European Symposium on Algorithms, ESA 2021"},{"key":"ref_61","unstructured":"Koana, T., Nichterlein, A., and W\u00fcnsche, N. (2022). Kernelization for Partial Vertex Cover via (Additive) Expansion Lemma. arXiv."},{"key":"ref_62","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1007\/BF01580444","article-title":"Vertex packings: Structural properties and algorithms","volume":"8","author":"Nemhauser","year":"1975","journal-title":"Math. Program."},{"key":"ref_63","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1016\/j.tcs.2020.06.001","article-title":"Quadratic vertex kernel for split vertex deletion","volume":"833","author":"Agrawal","year":"2020","journal-title":"Theor. Comput. Sci."},{"key":"ref_64","first-page":"18:1","article-title":"Parameterized Complexity of Deletion to Scattered Graph Classes","volume":"Volume 180","author":"Cao","year":"2020","journal-title":"Proceedings of the 15th International Symposium on Parameterized and Exact Computation, IPEC 2020"},{"key":"ref_65","first-page":"314","article-title":"Faster FPT Algorithms for Deletion to Pairs of Graph Classes","volume":"Volume 12867","author":"Bampis","year":"2021","journal-title":"Proceedings of the Fundamentals of Computation Theory\u201423rd International Symposium, FCT 2021"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/16\/3\/144\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T18:49:23Z","timestamp":1760122163000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/16\/3\/144"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,6]]},"references-count":65,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2023,3]]}},"alternative-id":["a16030144"],"URL":"https:\/\/doi.org\/10.3390\/a16030144","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,3,6]]}}}