{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,20]],"date-time":"2026-07-20T17:25:12Z","timestamp":1784568312951,"version":"3.55.0"},"reference-count":53,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2023,4,15]],"date-time":"2023-04-15T00:00:00Z","timestamp":1681516800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Research Council","award":["306992"],"award-info":[{"award-number":["306992"]}]},{"name":"PaPaAlg","award":["715744"],"award-info":[{"award-number":["715744"]}]},{"name":"SYSTEM-ATICGRAPH","award":["725978"],"award-info":[{"award-number":["725978"]}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["1176\/18"],"award-info":[{"award-number":["1176\/18"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]},{"name":"New Faculty Initiation","award":["NFIG008972"],"award-info":[{"award-number":["NFIG008972"]}]},{"DOI":"10.13039\/501100001843","name":"Science and Engineering Research Board","doi-asserted-by":"crossref","award":["SRG\/2002\/000962"],"award-info":[{"award-number":["SRG\/2002\/000962"]}],"id":[{"id":"10.13039\/501100001843","id-type":"DOI","asserted-by":"crossref"}]},{"name":"NSF","award":["CCF2008838"],"award-info":[{"award-number":["CCF2008838"]}]},{"name":"European Research Council"},{"name":"European Union\u2019s Horizon 2020","award":["819416"],"award-info":[{"award-number":["819416"]}]},{"name":"Swarnajayanti Fellowship","award":["DST\/SJF\/MSA01\/2017-18"],"award-info":[{"award-number":["DST\/SJF\/MSA01\/2017-18"]}]},{"name":"European Research Council"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2023,4,30]]},"abstract":"<jats:p>\n            Given a graph\n            <jats:italic>G<\/jats:italic>\n            and an integer\n            <jats:italic>k<\/jats:italic>\n            , the\n            <jats:sc>Interval Vertex Deletion (IVD)<\/jats:sc>\n            problem asks whether there exists a subset\n            <jats:italic>S<\/jats:italic>\n            \u2286\n            <jats:italic>V<\/jats:italic>\n            (\n            <jats:italic>G<\/jats:italic>\n            ) of size at most\n            <jats:italic>k<\/jats:italic>\n            such that\n            <jats:italic>G-S<\/jats:italic>\n            is an interval graph. This problem is known to be\n            <jats:sans-serif>NP<\/jats:sans-serif>\n            -complete (according to Yannakakis at STOC 1978). Originally in 2012, Cao and Marx showed that\n            <jats:sc>IVD<\/jats:sc>\n            is fixed parameter tractable: they exhibited an algorithm with running time 10\n            <jats:sup>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>O<\/jats:sup>\n            (1). The existence of a polynomial kernel for\n            <jats:sc>IVD<\/jats:sc>\n            remained a well-known open problem in parameterized complexity. In this article, we settle this problem in the affirmative.\n          <\/jats:p>","DOI":"10.1145\/3571075","type":"journal-article","created":{"date-parts":[[2023,1,19]],"date-time":"2023-01-19T13:15:57Z","timestamp":1674134157000},"page":"1-68","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Polynomial Kernel for Interval Vertex Deletion"],"prefix":"10.1145","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0656-7572","authenticated-orcid":false,"given":"Akanksha","family":"Agrawal","sequence":"first","affiliation":[{"name":"Indian Institute of Technology Madras, Chennai, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3166-9212","authenticated-orcid":false,"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[{"name":"University of California, Santa Barbara, Santa Barbara, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7086-5590","authenticated-orcid":false,"given":"Pranabendu","family":"Misra","sequence":"additional","affiliation":[{"name":"Chennai Mathematical Institute, Chennai, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7847-6402","authenticated-orcid":false,"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[{"name":"Homi Bhabha National Institute, Chennai, India, and University of Bergen, Bergen, Norway"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3636-5322","authenticated-orcid":false,"given":"Meirav","family":"Zehavi","sequence":"additional","affiliation":[{"name":"Ben-Gurion University, Beersheba, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,4,15]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"crossref","unstructured":"Akanksha Agrawal Sudeshna Kolay Daniel Lokshtanov and Saket Saurabh. 2016. A faster FPT algorithm and a smaller kernel for block graph vertex deletion. In LATIN 2016: Theoretical Informatics . Lecture Notes in Computer Science Vol. 9644. Springer 1\u201313.","DOI":"10.1007\/978-3-662-49529-2_1"},{"key":"e_1_3_2_3_2","first-page":"1383","volume-title":"Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201917)","author":"Agrawal Akanksha","year":"2017","unstructured":"Akanksha Agrawal, Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh, and Meirav Zehavi. 2017. Feedback vertex set inspired kernel for chordal vertex deletion. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201917). SIAM, 1383\u20131398."},{"issue":"1","key":"e_1_3_2_4_2","first-page":"Article 11, 28","article-title":"Feedback vertex set inspired kernel for chordal vertex deletion","volume":"15","author":"Agrawal Akanksha","year":"2019","unstructured":"Akanksha Agrawal, Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh, and Meirav Zehavi. 2019. Feedback vertex set inspired kernel for chordal vertex deletion. ACM Transactions on Algorithms 15, 1 (2019), Article 11, 28 pages.","journal-title":"ACM Transactions on Algorithms"},{"issue":"4","key":"e_1_3_2_5_2","first-page":"Article 18, 25","article-title":"Simultaneous feedback vertex set: A parameterized perspective","volume":"10","author":"Agrawal Akanksha","year":"2018","unstructured":"Akanksha Agrawal, Daniel Lokshtanov, Amer E. Mouawad, and Saket Saurabh. 2018. Simultaneous feedback vertex set: A parameterized perspective. ACM Transactions on Computation Theory 10, 4 (2018), Article 18, 25 pages.","journal-title":"ACM Transactions on Computation Theory"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/502102.502107"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.04.001"},{"issue":"3","key":"e_1_3_2_8_2","first-page":"447","article-title":"On generalized graphs","volume":"16","author":"Bollob\u00e1s B\u00e9la","year":"1965","unstructured":"B\u00e9la Bollob\u00e1s. 1965. On generalized graphs. Acta Mathematica Hungarica 16, 3-4 (1965), 447\u2013452.","journal-title":"Acta Mathematica Hungarica"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719796"},{"key":"e_1_3_2_10_2","first-page":"1096","volume-title":"Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201916)","author":"Cao Yixin","year":"2016","unstructured":"Yixin Cao. 2016. Linear recognition of almost interval graphs. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201916). SIAM, 1096\u20131115."},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2017.01.008"},{"issue":"3","key":"e_1_3_2_12_2","first-page":"Article 21, 35","article-title":"Interval deletion is fixed-parameter tractable","volume":"11","author":"Cao Yixin","year":"2015","unstructured":"Yixin Cao and D\u00e1niel Marx. 2015. Interval deletion is fixed-parameter tractable. ACM Transactions on Algorithms 11, 3 (2015), Article 21, 35 pages.","journal-title":"ACM Transactions on Algorithms"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-015-0014-x"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.5555\/2815661"},{"key":"e_1_3_2_15_2","unstructured":"Marek Cygan \u0141ukasz Kowalik and Marcin Pilipczuk. 2013. Open problems from Workshop on Kernels."},{"key":"e_1_3_2_16_2","first-page":"68","volume-title":"Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201912)","author":"Dell Holger","year":"2012","unstructured":"Holger Dell and D\u00e1niel Marx. 2012. Kernelization of packing problems. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201912). SIAM, 68\u201381."},{"issue":"4","key":"e_1_3_2_17_2","first-page":"Article 23, 27","article-title":"Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses","volume":"61","author":"Dell Holger","year":"2014","unstructured":"Holger Dell and Dieter van Melkebeek. 2014. Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. Journal of the ACM 61, 4 (2014), Article 23, 27 pages.","journal-title":"Journal of the ACM"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14279-6"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1137\/130927115"},{"key":"e_1_3_2_21_2","volume-title":"Parameterized Complexity Theory","author":"Flum J\u00f6rg","year":"2006","unstructured":"J\u00f6rg Flum and Martin Grohe. 2006. Parameterized Complexity Theory. Springer-Verlag, Berlin, Germany."},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2013.09.004"},{"key":"e_1_3_2_23_2","doi-asserted-by":"crossref","first-page":"470","DOI":"10.1109\/FOCS.2012.62","volume-title":"Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201912)","author":"Fomin Fedor V.","year":"2012","unstructured":"Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh. 2012. Planar f-deletion: Approximation, kernelization and optimal FPT algorithms. In Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201912). IEEE, Los Alamitos, CA, 470\u2013479."},{"issue":"4","key":"e_1_3_2_24_2","first-page":"Article 29, 60","article-title":"Efficient computation of representative families with applications in parameterized and exact algorithms","volume":"63","author":"Fomin Fedor V.","year":"2016","unstructured":"Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. 2016. Efficient computation of representative families with applications in parameterized and exact algorithms. Journal of the ACM 63, 4 (2016), Article 29, 60 pages.","journal-title":"Journal of the ACM"},{"key":"e_1_3_2_25_2","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1017\/CBO9781139177801.010","volume-title":"Tractability: Practical Approaches to Hard Problems","author":"Fomin Fedor V.","year":"2014","unstructured":"Fedor V. Fomin and Saket Saurabh. 2014. Kernelization methods for fixed-parameter tractability. In Tractability: Practical Approaches to Hard Problems, L. Bordeaux, Y. Hamadi, and P. Kohli (Eds.). Cambridge University Press, Cambridge, UK, 260\u2013282."},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.06.007"},{"key":"e_1_3_2_27_2","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1016\/S0166-218X(98)00035-3","article-title":"A unified approximation algorithm for node-deletion problems","volume":"86","author":"Fujito Toshihiro","year":"1998","unstructured":"Toshihiro Fujito. 1998. A unified approximation algorithm for node-deletion problems. Discrete Applied Mathematics 86, 2-3 (1998), 213\u2013231.","journal-title":"Discrete Applied Mathematics"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1965.15.835"},{"key":"e_1_3_2_29_2","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"Golumbic Martin Charles","year":"1980","unstructured":"Martin Charles Golumbic. 1980. Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York, NY."},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/1233481.1233493"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9910-8"},{"key":"e_1_3_2_32_2","first-page":"104","volume-title":"Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201912)","author":"Hermelin Danny","year":"2012","unstructured":"Danny Hermelin and Xi Wu. 2012. Weak compositions and their applications to polynomial lower bounds for kernelization. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201912). SIAM, 104\u2013113."},{"key":"e_1_3_2_33_2","volume-title":"The Power of Data Reduction: Kernels for Fundamental Graph Problems","author":"Jansen Bart M. P.","year":"2013","unstructured":"Bart M. P. Jansen. 2013. The Power of Data Reduction: Kernels for Fundamental Graph Problems. Ph.D. Dissertation. Utrecht University."},{"key":"e_1_3_2_34_2","first-page":"1802","volume-title":"Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201914)","author":"Jansen Bart M. P.","year":"2014","unstructured":"Bart M. P. Jansen, Daniel Lokshtanov, and Saket Saurabh. 2014. A near-optimal planarization algorithm. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201914). SIAM, 1802\u20131811."},{"key":"e_1_3_2_35_2","first-page":"1399","volume-title":"Proceedings of the T28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201917)","author":"Jansen Bart M. P.","year":"2017","unstructured":"Bart M. P. Jansen and Marcin Pilipczuk. 2017. Approximation and kernelization for chordal vertex deletion. In Proceedings of the T28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201917). SIAM, 1399\u20131418."},{"key":"e_1_3_2_36_2","first-page":"1399","volume-title":"Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201917","author":"Jansen Bart M. P.","year":"2017","unstructured":"Bart M. P. Jansen and Marcin Pilipczuk. 2017. Approximation and kernelization for chordal vertex deletion. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201917. SIAM, 1399\u20131418."},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1137\/17M112035X"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2018.01.001"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1969.28.565"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-017-0316-2"},{"issue":"2","key":"e_1_3_2_41_2","first-page":"Article 21, 41","article-title":"Linear kernels and single-exponential algorithms via protrusion decompositions","volume":"12","author":"Kim Eun Jung","year":"2016","unstructured":"Eun Jung Kim, Alexander Langer, Christophe Paul, Felix Reidl, Peter Rossmanith, Ignasi Sau, and Somnath Sikdar. 2016. Linear kernels and single-exponential algorithms via protrusion decompositions. ACM Transactions on Algorithms 12, 2 (2016), Article 21, 41 pages.","journal-title":"ACM Transactions on Algorithms"},{"key":"e_1_3_2_42_2","unstructured":"Stefan Kratsch. 2014. Recent developments in kernelization: A survey."},{"key":"e_1_3_2_43_2","doi-asserted-by":"crossref","first-page":"450","DOI":"10.1109\/FOCS.2012.46","volume-title":"Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201912)","author":"Kratsch Stefan","year":"2012","unstructured":"Stefan Kratsch and Magnus Wahlstr\u00f6m. 2012. Representative sets and irrelevant vertices: New tools for kernelization. In Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201912). IEEE, Los Alamitos, CA, 450\u2013459."},{"key":"e_1_3_2_44_2","volume-title":"Linear Algebra and Its Applications","author":"Lay David C.","year":"2006","unstructured":"David C. Lay. 2006. Linear Algebra and Its Applications. Pearson\/Addison-Wesley."},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.4064\/fm-51-1-45-64"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90060-4"},{"key":"e_1_3_2_47_2","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1007\/978-3-642-30891-8_10","volume-title":"The Multivariate Algorithmic Revolution and Beyond: Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday","author":"Lokshtanov Daniel","year":"2012","unstructured":"Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh. 2012. Kernelization\u2014Preprocessing with a guarantee. In The Multivariate Algorithmic Revolution and Beyond: Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday. Springer, Heidelberg, Germany, 129\u2013161."},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(72)90045-7"},{"key":"e_1_3_2_49_2","doi-asserted-by":"crossref","first-page":"960","DOI":"10.1145\/185675.306789","article-title":"On the hardness of approximating minimization problems","volume":"41","author":"Lund Carsten","year":"1994","unstructured":"Carsten Lund and Mihalis Yannakakis. 1994. On the hardness of approximating minimization problems. Journal of the ACM 41, 5 (1994), 960\u2013981.","journal-title":"Journal of the ACM"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.07.027"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-008-9233-8"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"e_1_3_2_53_2","volume-title":"Matroid Theory","author":"Oxley James G.","year":"2006","unstructured":"James G. Oxley. 2006. Matroid Theory. Vol. 3. Oxford University Press, New York, NY."},{"key":"e_1_3_2_54_2","first-page":"253","volume-title":"Proceedings of the 10th Annual ACM Symposium on Theory of Computing (STOC\u201978)","author":"Yannakakis Mihalis","year":"1978","unstructured":"Mihalis Yannakakis. 1978. Node- and edge-deletion NP-complete problems. In Proceedings of the 10th Annual ACM Symposium on Theory of Computing (STOC\u201978). ACM, New York, NY, 253\u2013264."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3571075","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3571075","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:08:20Z","timestamp":1750183700000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3571075"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,15]]},"references-count":53,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,4,30]]}},"alternative-id":["10.1145\/3571075"],"URL":"https:\/\/doi.org\/10.1145\/3571075","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,4,15]]},"assertion":[{"value":"2020-02-18","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-09-26","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-04-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}