2026-07-21T03:09:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25501 2026-03-19T13:34:14Z ddc:004 open_access

Density Matters: A Complexity Dichotomy of Deleting Edges to Bound Subgraph Density Bentert, Matthias Breitkopf, Tom-Lukas Froese, Vincent Herrmann, Anton Nichterlein, André Transshipment Maximum Flow General Factors Matching Graph Modification Problem 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Matthias Bentert and Tom-Lukas Breitkopf and Vincent Froese and Anton Herrmann and André Nichterlein 2026 Is Part Of LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2026.12 urn:nbn:de:0030-drops-255012 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.12 eng https://creativecommons.org/licenses/by/4.0/legalcode