{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T01:32:52Z","timestamp":1742952772100,"version":"3.40.3"},"publisher-location":"Cham","reference-count":26,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031159138"},{"type":"electronic","value":"9783031159145"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,10,1]],"date-time":"2022-10-01T00:00:00Z","timestamp":1664582400000},"content-version":"vor","delay-in-days":273,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study efficient preprocessing for the undirected <jats:sc>Feedback Vertex Set<\/jats:sc> problem, a fundamental problem in graph theory which asks for a minimum-sized vertex set whose removal yields an acyclic graph. More precisely, we aim to determine for which parameterizations this problem admits a polynomial kernel. While a characterization is known for the related <jats:sc>Vertex Cover<\/jats:sc> problem based on the recently introduced notion of bridge-depth, it remained an open problem whether this could be generalized to <jats:sc>Feedback Vertex Set<\/jats:sc>. The answer turns out to be negative; the existence of polynomial kernels for structural parameterizations for <jats:sc>Feedback Vertex Set<\/jats:sc> is governed by the elimination distance to a forest. Under the standard assumption <jats:inline-formula><jats:tex-math>$$\\textrm{NP}\\not \\subseteq \\textrm{coNP}\/\\textrm{poly}$$<\/jats:tex-math><\/jats:inline-formula>, we prove that for any minor-closed graph class <jats:inline-formula><jats:tex-math>$$\\mathcal {G}$$<\/jats:tex-math><\/jats:inline-formula>, <jats:sc>Feedback Vertex Set<\/jats:sc> parameterized by the size of a modulator to <jats:inline-formula><jats:tex-math>$$\\mathcal {G}$$<\/jats:tex-math><\/jats:inline-formula> has a polynomial kernel if and only if <jats:inline-formula><jats:tex-math>$$\\mathcal {G}$$<\/jats:tex-math><\/jats:inline-formula> has bounded elimination distance to a forest. This captures and generalizes all existing kernels for structural parameterizations of the <jats:sc>Feedback Vertex Set<\/jats:sc> problem.<\/jats:p>","DOI":"10.1007\/978-3-031-15914-5_12","type":"book-chapter","created":{"date-parts":[[2022,9,30]],"date-time":"2022-09-30T11:14:22Z","timestamp":1664536462000},"page":"158-172","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Kernelization for\u00a0Feedback Vertex Set via\u00a0Elimination Distance to\u00a0a\u00a0Forest"],"prefix":"10.1007","author":[{"given":"David","family":"Dekker","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bart M. P.","family":"Jansen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,10,1]]},"reference":[{"issue":"3","key":"12_CR1","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1007\/s00224-007-1328-0","volume":"41","author":"FN Abu-Khzam","year":"2007","unstructured":"Abu-Khzam, F.N., Fellows, M.R., Langston, M.A., Suters, W.H.: Crown structures for vertex cover kernelization. Theor. Comput. Syst. 41(3), 411\u2013430 (2007). https:\/\/doi.org\/10.1007\/s00224-007-1328-0","journal-title":"Theor. Comput. Syst."},{"issue":"3","key":"12_CR2","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1007\/s00224-009-9234-2","volume":"46","author":"HL Bodlaender","year":"2010","unstructured":"Bodlaender, H.L., van Dijk, T.C.: A cubic kernel for feedback vertex set and loop cutset. Theor. Comput. Syst. 46(3), 566\u2013597 (2010). https:\/\/doi.org\/10.1007\/s00224-009-9234-2","journal-title":"Theor. Comput. Syst."},{"key":"12_CR3","doi-asserted-by":"publisher","unstructured":"Bougeret, M., Jansen, B.M.P., Sau, I.: Bridge-depth characterizes which structural parameterizations of vertex cover admit a polynomial kernel. In: Czumaj, A., Dawar, A., Merelli, E. (eds.) 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, 8\u201311 July 2020, Saarbr\u00fccken, Germany (Virtual Conference). LIPIcs, vol. 168, pp. 1\u201319. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2020.16","DOI":"10.4230\/LIPIcs.ICALP.2020.16"},{"issue":"10","key":"12_CR4","doi-asserted-by":"publisher","first-page":"4043","DOI":"10.1007\/s00453-018-0468-8","volume":"81","author":"M Bougeret","year":"2018","unstructured":"Bougeret, M., Sau, I.: How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs? Algorithmica 81(10), 4043\u20134068 (2018). https:\/\/doi.org\/10.1007\/s00453-018-0468-8","journal-title":"Algorithmica"},{"issue":"1","key":"12_CR5","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/s00453-016-0235-7","volume":"79","author":"J Bulian","year":"2016","unstructured":"Bulian, J., Dawar, A.: Fixed-parameter tractable distances to sparse graph classes. Algorithmica 79(1), 139\u2013158 (2016). https:\/\/doi.org\/10.1007\/s00453-016-0235-7","journal-title":"Algorithmica"},{"key":"12_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1007\/11847250_18","volume-title":"Parameterized and Exact Computation","author":"K Burrage","year":"2006","unstructured":"Burrage, K., Estivill-Castro, V., Fellows, M., Langston, M., Mac, S., Rosamond, F.: The undirected feedback vertex set problem has a poly(k) kernel. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol. 4169, pp. 192\u2013202. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11847250_18"},{"issue":"2","key":"12_CR7","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1006\/jagm.2001.1186","volume":"41","author":"J Chen","year":"2001","unstructured":"Chen, J., Kanj, I.A., Jia, W.: Vertex cover: further observations and further improvements. J. Algorithms 41(2), 280\u2013301 (2001). https:\/\/doi.org\/10.1006\/jagm.2001.1186","journal-title":"J. Algorithms"},{"issue":"3","key":"12_CR8","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1016\/j.dam.2007.03.026","volume":"156","author":"M Chleb\u00edk","year":"2008","unstructured":"Chleb\u00edk, M., Chleb\u00edkov\u00e1, J.: Crown reductions for the minimum weighted vertex cover problem. Discret. Appl. Math. 156(3), 292\u2013312 (2008). https:\/\/doi.org\/10.1016\/j.dam.2007.03.026","journal-title":"Discret. Appl. Math."},{"key":"12_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/978-3-540-30559-0_22","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"B Chor","year":"2004","unstructured":"Chor, B., Fellows, M., Juedes, D.: Linear kernels in linear time, or how to save k colors in O(n2) steps. In: Hromkovi\u010d, J., Nagl, M., Westfechtel, B. (eds.) WG 2004. LNCS, vol. 3353, pp. 257\u2013269. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-30559-0_22"},{"key":"12_CR10","unstructured":"Dekker, D., Jansen, B.M.P.: Kernelization for feedback vertex set via elimination distance to a forest. CoRR abs\/2206.04387 (2022). https:\/\/doi.org\/10.48550\/arXiv. 2206.04387"},{"issue":"4","key":"12_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2629620","volume":"61","author":"H Dell","year":"2014","unstructured":"Dell, H., van Melkebeek, D.: Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. J. ACM 61(4), 1\u201327 (2014). https:\/\/doi.org\/10.1145\/2629620","journal-title":"J. ACM"},{"key":"12_CR12","series-title":"Texts in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. TCS, Springer, London (2013). https:\/\/doi.org\/10.1007\/978-1-4471-5559-1"},{"issue":"4","key":"12_CR13","doi-asserted-by":"publisher","first-page":"822","DOI":"10.1007\/s00224-009-9167-9","volume":"45","author":"MR Fellows","year":"2009","unstructured":"Fellows, M.R., Lokshtanov, D., Misra, N., Mnich, M., Rosamond, F.A., Saurabh, S.: The complexity ecology of parameters: an illustration using bounded max leaf number. Theor. Comput. Syst. 45(4), 822\u2013848 (2009). https:\/\/doi.org\/10.1007\/s00224-009-9167-9","journal-title":"Theor. Comput. Syst."},{"key":"12_CR14","doi-asserted-by":"publisher","unstructured":"Fomin, F.V., Lokshtanov, D., Misra, N., Saurabh, S.: Planar $$\\cal{F} $$-Deletion: approximation, kernelization and optimal FPT algorithms. In: 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, 20\u201323 October 2012, pp. 470\u2013479. IEEE Computer Society (2012). https:\/\/doi.org\/10.1109\/FOCS.2012.62","DOI":"10.1109\/FOCS.2012.62"},{"key":"12_CR15","doi-asserted-by":"publisher","unstructured":"Hols, E.C., Kratsch, S.: Smaller parameters for vertex cover kernelization. In: Lokshtanov, D., Nishimura, N. (eds.) 12th International Symposium on Parameterized and Exact Computation, IPEC 2017, 6\u20138 September 2017, Vienna, Austria. LIPIcs, vol. 89, pp. 1\u201312. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2017). https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2017.20","DOI":"10.4230\/LIPIcs.IPEC.2017.20"},{"key":"12_CR16","doi-asserted-by":"publisher","unstructured":"Iwata, Y.: Linear-time kernelization for feedback vertex set. In: Chatzigiannakis, I., Indyk, P., Kuhn, F., Muscholl, A. (eds.) 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, 10\u201314 July 2017, Warsaw, Poland. LIPIcs, vol. 80, pp. 1\u201314. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2017). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2017.68","DOI":"10.4230\/LIPIcs.ICALP.2017.68"},{"issue":"4","key":"12_CR17","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1109\/TST.2014.6867520","volume":"19","author":"B Jansen","year":"2014","unstructured":"Jansen, B., Raman, V., Vatshelle, M.: Parameter ecology for feedback vertex set. Tsinghua Sci.Technol. 19(4), 387\u2013409 (2014). https:\/\/doi.org\/10.1109\/TST.2014.6867520","journal-title":"Tsinghua Sci.Technol."},{"issue":"2","key":"12_CR18","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/s00224-012-9393-4","volume":"53","author":"BMP Jansen","year":"2012","unstructured":"Jansen, B.M.P., Bodlaender, H.L.: Vertex cover kernelization revisited. Theor. Comput. Syst. 53(2), 263\u2013299 (2012). https:\/\/doi.org\/10.1007\/s00224-012-9393-4","journal-title":"Theor. Comput. Syst."},{"key":"12_CR19","doi-asserted-by":"publisher","unstructured":"Jansen, B.M.P., de Kroon, J.J.H., W\u0142odarczyk, M.: Vertex deletion parameterized by elimination distance and even less. In: Khuller, S., Williams, V.V. (eds.) STOC \u201921: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, 21\u201325 June 2021, pp. 1757\u20131769. ACM (2021). https:\/\/doi.org\/10.1145\/3406325.3451068","DOI":"10.1145\/3406325.3451068"},{"key":"12_CR20","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1016\/j.tcs.2020.07.009","volume":"841","author":"BMP Jansen","year":"2020","unstructured":"Jansen, B.M.P., Pieterse, A.: Polynomial kernels for hitting forbidden minors under structural parameterizations. Theor. Comput. Sci. 841, 124\u2013166 (2020). https:\/\/doi.org\/10.1016\/j.tcs.2020.07.009","journal-title":"Theor. Comput. Sci."},{"key":"12_CR21","doi-asserted-by":"publisher","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Proceedings of a symposium on the Complexity of Computer Computations, Held 20\u201322 March 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, USA. The IBM Research Symposia Series, pp. 85\u2013103. Plenum Press, New York (1972). https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"9","key":"12_CR22","doi-asserted-by":"publisher","first-page":"2683","DOI":"10.1007\/s00453-018-0419-4","volume":"80","author":"D Majumdar","year":"2018","unstructured":"Majumdar, D., Raman, V.: Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization. Algorithmica 80(9), 2683\u20132724 (2018). https:\/\/doi.org\/10.1007\/s00453-018-0419-4","journal-title":"Algorithmica"},{"issue":"8","key":"12_CR23","doi-asserted-by":"publisher","first-page":"1910","DOI":"10.1007\/s00224-018-9858-1","volume":"62","author":"D Majumdar","year":"2018","unstructured":"Majumdar, D., Raman, V., Saurabh, S.: Polynomial kernels for vertex cover parameterized by small degree modulators. Theor. Comput. Syst. 62(8), 1910\u20131951 (2018). https:\/\/doi.org\/10.1007\/s00224-018-9858-1","journal-title":"Theor. Comput. Syst."},{"issue":"1","key":"12_CR24","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/BF01580444","volume":"8","author":"GL Nemhauser Jr","year":"1975","unstructured":"Nemhauser, G.L., Jr., Trotter, L.E.: Vertex packings: structural properties and algorithms. Math. Program. 8(1), 232\u2013248 (1975). https:\/\/doi.org\/10.1007\/BF01580444","journal-title":"Math. Program."},{"key":"12_CR25","doi-asserted-by":"publisher","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: Sparsity - Graphs, Structures, and Algorithms, Algorithms and Combinatorics, vol. 28. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-27875-4","DOI":"10.1007\/978-3-642-27875-4"},{"key":"12_CR26","unstructured":"Thomass\u00e9, S.: A quadratic kernel for feedback vertex set. In: Mathieu, C. (ed.) Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, 4\u20136 January 2009, pp. 115\u2013119. SIAM (2009). http:\/\/dl.acm.org\/citation.cfm?id=1496770.1496783"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-15914-5_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,30]],"date-time":"2022-09-30T11:20:18Z","timestamp":1664536818000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-15914-5_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031159138","9783031159145"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-15914-5_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"1 October 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WG","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Graph-Theoretic Concepts in Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"T\u00fcbingen","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 June 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 June 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"48","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wg2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/algo.inf.uni-tuebingen.de\/wg2022\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"96","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"32","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"33% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"12","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}