View PDF HTML (experimental)

Abstract:We explore the parameterized complexity of Bounded Density Vertex Deletion (BDVD): given a graph $G$, an integer budget $k$, and a target density $\tau_\rho$, 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 $\tau_\rho$ 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 $\tau_\rho$ 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.

Submission history

From: Anton Herrmann [view email]
[v1] Wed, 24 Jun 2026 16:31:03 UTC (238 KB)