  We analyze the computational complexity of the following computational
problems called Bounded-Density Edge Deletion and Bounded-Density Vertex
Deletion: Given a graph $G$, a budget $k$ and a target density $\tau_\rho$, are
there $k$ edges ($k$ vertices) whose removal from $G$ results in a graph where
the densest subgraph has density at most $\tau_\rho$? Here, the density of a
graph is the number of its edges divided by the number of its vertices. We
prove that both problems are polynomial-time solvable on trees and cliques but
are NP-complete on planar bipartite graphs and split graphs. From a
parameterized point of view, we show that both problems are fixed-parameter
tractable with respect to the vertex cover number but W[1]-hard with respect to
the solution size. Furthermore, we prove that Bounded-Density Edge Deletion is
W[1]-hard with respect to the feedback edge number, demonstrating that the
problem remains hard on very sparse graphs.
