Density Matters: A Complexity Dichotomy of Deleting Edges to Bound Subgraph Density

We study τ-Bounded-Density Edge Deletion (τ-BDED), where given an undirected graph G, the task is to remove as few edges as possible to obtain a graph G' where no subgraph of G' has density more than τ. The density of a (sub) graph is the number of edges divided by the number of vertices. This problem was recently introduced and shown to be NP-hard for τ ∈ 2/3, 3/4, 1 + 1/25, but polynomial-time solvable for τ ∈ 0, 1/2, 1 Bazgan et al. , JCSS 2025. We provide a complete dichotomy with respect to the target density τ: 1) If 2τ ∈ ℕ (half-integral target density) or τ < 2/3, then τ-BDED is polynomial-time solvable. 2) Otherwise, τ-BDED is NP-hard. We complement the NP-hardness with fixed-parameter tractability with respect to the treewidth of G. Moreover, for integral target density τ ∈ ℕ, we show τ-BDED to be solvable in randomized O (m^1 + o (1) ) time. Our algorithmic results are based on a reduction to a new general flow problem on restricted networks that, depending on τ, can be solved via Maximum s-t-Flow or General Factors. We believe this connection between these variants of flow and matching to be of independent interest.