Parameterized Vertex Deletion Problems for Hereditary Graph Classes with a Block Property

For a class of graphs P, the Bounded P-Block Vertex Deletion problem asks, given a graph G on n vertices and positive integers k and d, whether there is a set S of at most k vertices such that each block of G - S has at most d vertices and is in P. We show that when P satisfies a natural hereditary property and is recognizable in polynomial time, Bounded P-Block Vertex Deletion can be solved in time 2(O(k log d))n(O(1)), and this running time cannot be improved to 2(o(k log d))n(O(1)), in general, unless the Exponential Time Hypothesis fails. On the other hand, if P consists of only complete graphs, or only K-1, K-2, and cycle graphs, then Bounded P-Block Vertex Deletion admits a c(k) n(O(1))-time algorithm for some constant c independent of d. We also show that Bounded P-Block Vertex Deletion admits a kernel with O(k(2)d(7)) vertices.