On the Parameterized Complexity of Bounded-Density Vertex Deletion
This work provides a refined complexity landscape for BDVD, distinguishing tractable and intractable parameter regimes, which is important for algorithm design in graph theory.
The paper resolves the open question of the parameterized complexity of Bounded Density Vertex Deletion (BDVD) with respect to treewidth, showing W[1]-hardness for treedepth and feedback vertex number, implying hardness for treewidth. Positive results are obtained for max leaf number and vertex integrity, and fixed-parameter tractability for cliquewidth when target density is constant.
We explore the parameterized complexity of Bounded Density Vertex Deletion (BDVD): given a graph $G$, an integer budget $k$, and a target density $τ_ρ$, the task is to determine whether the density (i.e. number of edges divided by number of vertices) of the densest subgraph of $G$ can be reduced to at most $τ_ρ$ by deleting at most $k$ vertices. Our primary focus is on structural graph parameters related to treewidth, as the parameterized complexity of BDVD with respect to treewidth was left as open question by Bazgan et al. [JCSS, 2025]. We resolve this question by showing W[1]-hardness with respect to various parameters, including treedepth and feedback vertex number. These results imply W[1]-hardness with respect to treewidth. We obtain positive results for parameters larger than treedepth and feedback vertex number, namely we show BDVD is in FPT parameterized by the max leaf number or vertex integrity. Under the assumption that the target density $τ_ρ$ is a fixed constant the parameterized complexity landscape of BDVD changes drastically, allowing a fixed-parameter tractable algorithm even for parameters smaller than treewidth, namely cliquewidth. Altogether, our results provide a refined complexity landscape for Bounded Density Vertex Deletion, sharply distinguishing between tractable and intractable parameter regimes under structural parameterizations.