2026-07-21T18:40:58Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8565 2024-03-06T10:41:30Z ddc:004 open_access

Generalized Feedback Vertex Set Problems on Bounded-Treewidth Graphs: Chordality Is the Key to Single-Exponential Parameterized Algorithms Bonnet, Édouard Brettell, Nick Kwon, O-joung Marx, Dániel fixed-parameter tractable algorithms treewidth feedback vertex set It has long been known that Feedback Vertex Set can be solved in time 2^O(w log w)n^O(1) on graphs of treewidth w, but it was only recently that this running time was improved to 2^O(w)n^O(1), that is, to single-exponential parameterized by treewidth. We investigate which generalizations of Feedback Vertex Set can be solved in a similar running time. Formally, for a class of graphs P, Bounded P-Block Vertex Deletion asks, given a graph G on n vertices and positive integers k and d, whether G contains a set S of at most k vertices such that each block of G-S has at most d vertices and is in P. Assuming that P is recognizable in polynomial time and satisfies a certain natural hereditary condition, we give a sharp characterization of when single-exponential parameterized algorithms are possible for fixed values of d: - if P consists only of chordal graphs, then the problem can be solved in time 2^O(wd^2) n^{O}(1), - if P contains a graph with an induced cycle of length ell>= 4, then the problem is not solvable in time 2^{o(w log w)} n^O(1)} even for fixed d=ell, unless the ETH fails. We also study a similar problem, called Bounded P-Component Vertex Deletion, where the target graphs have connected components of small size instead of having blocks of small size, and present analogous results. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Édouard Bonnet and Nick Brettell and O-joung Kwon and Dániel Marx 2018 Is Part Of LIPIcs, Volume 89, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2017.7 urn:nbn:de:0030-drops-85653 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.7 eng https://creativecommons.org/licenses/by/3.0/legalcode