{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:38:13Z","timestamp":1767339493623,"version":"3.41.0"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2018,12,8]],"date-time":"2018-12-08T00:00:00Z","timestamp":1544227200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Research Council under the European Unions Seventh Framework Programme ERC","award":["FP\/2007-2013 and 306992"],"award-info":[{"award-number":["FP\/2007-2013 and 306992"]}]},{"name":"ERC Starting","award":["715744"],"award-info":[{"award-number":["715744"]}]},{"name":"Pareto-Optimal Parameterized Algorithms"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2019,1,31]]},"abstract":"<jats:p>\n            Given a graph\n            <jats:italic>G<\/jats:italic>\n            and a parameter\n            <jats:italic>k<\/jats:italic>\n            , the C\n            <jats:sc>hordal<\/jats:sc>\n            V\n            <jats:sc>ertex<\/jats:sc>\n            D\n            <jats:sc>eletion<\/jats:sc>\n            (CVD) problem asks whether there exists a subset\n            <jats:italic>U<\/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            that hits all induced cycles of size at least 4. The existence of a polynomial kernel for CVD was a well-known open problem in the field of Parameterized Complexity. Recently, Jansen and Pilipczuk resolved this question affirmatively by designing a polynomial kernel for CVD of size\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>161<\/jats:sup>\n            log\n            <jats:sup>58<\/jats:sup>\n            <jats:italic>k<\/jats:italic>\n            ) and asked whether one can design a kernel of size\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>10<\/jats:sup>\n            ) [Jansen an Pilipczuk, SODA 2017]. While we do not completely resolve this question, we design a significantly smaller kernel of size\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>12<\/jats:sup>\n            log\n            <jats:sup>10<\/jats:sup>\n            <jats:italic>k<\/jats:italic>\n            ), inspired by the\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ) -size kernel for F\n            <jats:sc>eedback<\/jats:sc>\n            V\n            <jats:sc>ertex<\/jats:sc>\n            S\n            <jats:sc>et<\/jats:sc>\n            [Thomass\u00e9, TALG 2010]. Furthermore, we introduce the notion of the independence degree of a vertex, which is our main conceptual contribution.\n          <\/jats:p>","DOI":"10.1145\/3284356","type":"journal-article","created":{"date-parts":[[2018,12,10]],"date-time":"2018-12-10T13:09:16Z","timestamp":1544447356000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion"],"prefix":"10.1145","volume":"15","author":[{"given":"Akanksha","family":"Agrawal","sequence":"first","affiliation":[{"name":"Hungarian Academy of Sciences, Budapest, Hungary"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[{"name":"University of Bergen, Bergen, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pranabendu","family":"Misra","sequence":"additional","affiliation":[{"name":"University of Bergen, Bergen, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[{"name":"Institute of Mathematical Sciences, India and University of Bergen, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Meirav","family":"Zehavi","sequence":"additional","affiliation":[{"name":"Ben-Gurion University, Beersheba, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,12,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.09.002"},{"volume-title":"Proceedings of the 6th Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithmics and Combinatorics. 62--69","author":"Abu-Khzam Faisal N.","key":"e_1_2_1_2_1","unstructured":"Faisal N. Abu-Khzam , Rebecca L. Collins , Michael R. Fellows , Michael A. Langston , W. Henry Suters , and Christopher T. Symons . 2004. Kernelization algorithms for the vertex cover problem: Theory and experiments . In Proceedings of the 6th Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithmics and Combinatorics. 62--69 . Faisal N. Abu-Khzam, Rebecca L. Collins, Michael R. Fellows, Michael A. Langston, W. Henry Suters, and Christopher T. Symons. 2004. Kernelization algorithms for the vertex cover problem: Theory and experiments. In Proceedings of the 6th Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithmics and Combinatorics. 62--69."},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 21st Conference on Approximation, Randomization, Combinatorial Optimization, Algorithms and Techniques (APPROX\/RANDOM'18)","author":"Agrawal Akanksha","year":"2018","unstructured":"Akanksha Agrawal , Daniel Lokshtanov , Pranabendu Misra , Saket Saurabh , and Meirav Zehavi . 2018 . Polylogarithmic approximation algorithms for weighted-F-deletion problems . In Proceedings of the 21st Conference on Approximation, Randomization, Combinatorial Optimization, Algorithms and Techniques (APPROX\/RANDOM'18) . 1:1--1:15. Akanksha Agrawal, Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh, and Meirav Zehavi. 2018. Polylogarithmic approximation algorithms for weighted-F-deletion problems. In Proceedings of the 21st Conference on Approximation, Randomization, Combinatorial Optimization, Algorithms and Techniques (APPROX\/RANDOM'18). 1:1--1:15."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9428-7"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.04.001"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2973749"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/120903518"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884512"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629595"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-015-0014-x"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2001.1186"},{"volume-title":"Parameterized Algorithms","author":"Cygan Marek","key":"e_1_2_1_12_1","unstructured":"Marek Cygan , Fedor V. Fomin , \u0141ukasz Kowalik , Daniel Lokshtanov , Daniel Marx , Marcin Pilipczuk , Michal Pilipczuk , and Saket Saurabh . 2015. Parameterized Algorithms . Springer-Verlag . Marek Cygan, Fedor V. Fomin, \u0141ukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. 2015. Parameterized Algorithms. Springer-Verlag."},{"key":"e_1_2_1_13_1","unstructured":"Marek Cygan Lukasz Kowalik and Marcin Pilipczuk. 2013. Open problems from workshop on kernels. Retrieved from http:\/\/worker2013.mimuw.edu.pl\/slides\/worker-opl.pdf.  Marek Cygan Lukasz Kowalik and Marcin Pilipczuk. 2013. Open problems from workshop on kernels. Retrieved from http:\/\/worker2013.mimuw.edu.pl\/slides\/worker-opl.pdf."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629620"},{"key":"e_1_2_1_15_1","volume-title":"Fellows","author":"Downey Rodney G.","year":"2013","unstructured":"Rodney G. Downey and Michael R . Fellows . 2013 . Fundamentals of Parameterized Complexity. Springer . Rodney G. Downey and Michael R. Fellows. 2013. Fundamentals of Parameterized Complexity. Springer."},{"volume-title":"Parameterized Complexity Theory","author":"Flum J\u00f6rg","key":"e_1_2_1_16_1","unstructured":"J\u00f6rg Flum and Martin Grohe . 2006. Parameterized Complexity Theory . Springer-Verlag , Berlin . J\u00f6rg Flum and Martin Grohe. 2006. Parameterized Complexity Theory. Springer-Verlag, Berlin."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.62"},{"key":"e_1_2_1_18_1","volume-title":"Thilikos","author":"Fomin Fedor V.","year":"2010","unstructured":"Fedor V. Fomin , Daniel Lokshtanov , Saket Saurabh , and Dimitrios M . Thilikos . 2010 . Bidimensionality and kernels. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201910). 503--510. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Dimitrios M. Thilikos. 2010. Bidimensionality and kernels. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201910). 503--510."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/12089051X"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.06.007"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(98)00035-3"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47672-7_51"},{"volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"Golumbic Martin Charles","key":"e_1_2_1_23_1","unstructured":"Martin Charles Golumbic . 1980. Algorithmic Graph Theory and Perfect Graphs . Academic Press, New York , NY. Martin Charles Golumbic. 1980. Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York, NY."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.03.013"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44777-2_48"},{"key":"e_1_2_1_26_1","volume-title":"Jansen and Marcin Pilipczuk","author":"Bart M.","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'17). 1399--1418. 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'17). 1399--1418."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2018.01.001"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2797140"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/2150816.2150837"},{"key":"e_1_2_1_30_1","volume-title":"Recent developments in kernelization: A survey. Bull. EATCS 113","author":"Kratsch Stefan","year":"2014","unstructured":"Stefan Kratsch . 2014. Recent developments in kernelization: A survey. Bull. EATCS 113 ( 2014 ). Stefan Kratsch. 2014. Recent developments in kernelization: A survey. Bull. EATCS 113 (2014)."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.46"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2635810"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90060-4"},{"volume-title":"The Multivariate Algorithmic Revolution and Beyond\u2014Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday. 129--161.","author":"Lokshtanov Daniel","key":"e_1_2_1_34_1","unstructured":"Daniel Lokshtanov , Neeldhara Misra , and Saket Saurabh . 2012. Kernelization\u2014Preprocessing with a guarantee . In The Multivariate Algorithmic Revolution and Beyond\u2014Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday. 129--161. Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh. 2012. Kernelization\u2014Preprocessing with a guarantee. In The Multivariate Algorithmic Revolution and Beyond\u2014Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday. 129--161."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/185675.306789"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-008-9233-8"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2500119"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.37"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1721837.1721848"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804355"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3284356","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3284356","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:43:49Z","timestamp":1750207429000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3284356"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,12,8]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,1,31]]}},"alternative-id":["10.1145\/3284356"],"URL":"https:\/\/doi.org\/10.1145\/3284356","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2018,12,8]]},"assertion":[{"value":"2018-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-12-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}