2026-07-26T21:31:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20046 2024-05-31T13:11:10Z ddc:004 open_access

Destroying Densest Subgraphs Is Hard Bazgan, Cristina Nichterlein, André Vazquez Alferez, Sofia Graph modification problems NP-hardness fixed-parameter tractability W-hardness special graph classes 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 τ_ρ, are there k edges (k vertices) whose removal from G results in a graph where the densest subgraph has density at most τ_ρ? 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Cristina Bazgan and André Nichterlein and Sofia Vazquez Alferez 2024 Is Part Of LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2024.6 urn:nbn:de:0030-drops-200461 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.6 eng https://creativecommons.org/licenses/by/4.0/legalcode