Destroying Densest Subgraphs is Hard

Cristina Bazgan, André Nichterlein, Sofia Vazquez Alferez

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 budge…