For a class of graphs $\mathcal{ P}$, the Bounded $\mathcal{ 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 $\mathcal{ P}$. We show that when $\mathcal{ P}$ satisfies a natural hereditary property and is recognizable in polynomial time, Bounded $\mathcal{ P}$-Block Vertex Deletion can be solved in time $2^{ O(k \log d)}n^{ O(1)}$. When $\mathcal{ P}$ contains all split graphs, we show that this running time is essentially optimal unless the Exponential Time Hypothesis fails. On the other hand, if $\mathcal{ P}$ consists of only complete graphs, or only cycle graphs and $K_2$, then Bounded $\mathcal{ 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 $\mathcal{ P}$-Block Vertex Deletion admits a kernel with $O(k^2 d^7)$ vertices.
Categories: cs.DS