On the Parameterized Complexity of Bounded-Density Vertex Deletion

Jakob Raupach, Tom-Lukas Breitkopf, Anton Herrmann, André Nichterlein · 2026

Read On the Parameterized Complexity of Bounded-Density Vertex Deletion by Jakob Raupach, Tom-Lukas Breitkopf, Anton Herrmann, André Nichterlein (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-26012.txt.

Introduction

Jakob Raupach, Tom-Lukas Breitkopf, Anton Herrmann, and André Nichterlein study a graph problem about thinning out dense spots. Bounded Density Vertex Deletion asks a sharp question. Can deleting at most k vertices bring the densest subgraph's density under a target value? Density here means edges divided by vertices. Bazgan and colleagues had left the problem's difficulty open for treewidth, a standard measure of graph structure.

Hardness results settle most of the landscape. The problem is W-one-hard for treedepth and for feedback vertex number. Hardness for treewidth follows from those results. Two larger parameters rescue tractability. The problem is fixed-parameter tractable for max leaf number and for vertex integrity. Fixing the target density as a constant changes the picture again. Even cliquewidth, a parameter below treewidth, then admits an efficient algorithm. The map cleanly separates workable parameter regimes from hopeless ones.

Catalog record

CREATORJakob Raupach, Tom-Lukas Breitkopf, Anton Herrmann, André Nichterlein
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE76 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.26012

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On the Parameterized Complexity of Bounded-Density Vertex Deletion Jakob Raupach, Tom-Lukas Breitkopf, Anton Herrmann, André Nichterlein Abstract We explore the parameterized complexity of Bounded Density Vertex Deletion ( BDVD ): given a graph G G , an integer budget k k , and a target density τ ρ \tau_{\rho} , the task is to determine whether the density (i.e. number of edges divided by number of vertices) of the densest subgraph of G G can be reduced to at most τ ρ \tau_{\rho} by deleting at most k k vertices. Our primary focus is on structural graph parameters related to treewidth, as the parameterized complexity of BDVD with respect to treewidth was left as open question by Bazgan et al. [JCSS, 2025]. We resolve this question by showing W ⁡ [ 1 ] \W[1] -hardness with respect to various parameters, including treedepth and feedback vertex number. These results imply W ⁡ [ 1 ] \W[1] -hardness with respect to treewidth. We obtain positive results for parameters larger than treedepth and feedback vertex number, namely we show BDVD is in FPT \FPT parameterized by the max leaf number or vertex integrity. Under the assumption that the target density τ ρ \tau_{\rho} is a fixed constant the parameterized complexity landscape of BDVD changes drastically, allowing a fixed-parameter tractable algorithm even for parameters smaller than treewidth, namely cliquewidth. Altogether, our results provide a refined complexity landscape for Bounded Density Vertex Deletion , sharply distinguishing between tractable and intractable parameter regimes under structural parameterizations. \Crefname theoremThm.Thms. \crefname theoremTheoremTheorems Technische Universität Berlin, [email protected] Algorithmics and Computational Complexity, Technische Universität Berlin, [email protected]://orcid.org/0009-0008-2875-1945 Algorithmics and Computational Complexity, Technische Universität Berlin, [email protected]://orcid.org/0009-0008-8473-9043 Algorithmics and Computational Complexity, Technische Universität Berlin, [email protected]://orcid.org/0000-0001-7451-9401 keywords Graph Modification Problem, Integer Linear Programming, Dynamic Programming, Max Leaf Number, Vertex Integrity ccs Theory of computation Parameterized complexity and exact algorithms ccs Theory of computation Problems, reductions and completeness † † runningauthor: J. Raupach, T.-L. Breitkopf, A. Herrmann, A. Nichterlein † † copyright: Jakob Raupach, Tom-Lukas Breitkopf, Anton Herrmann, André Nichterlein † † editors: Michal Koucký and Daniela Petrişan † † event-title: 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026) † † event-shorttitle: MFCS 2026 † † event-acronym: MFCS † † year: 2026 † † event-date: August 24–28, 2026 † † event-location: Paris, France † † series-volume: 386 † † articleno: 62 1 Introduction The problem of identifying a densest subgraph constitutes a central topic in graph theory, with numerous applications across domains such as social network analysis, bioinformatics, and financial modeling [ 27 ] . This problem has been extensively studied, with the first polynomial-time algorithms proposed more than four decades ago [ 30 ] . In this work, we examine the stability of densest subgraphs under vertex deletions in the input graph. We investigate Bounded Density Vertex Deletion ( BDVD ), which asks whether it is possible to delete at most k vertices so that the density of the densest subgraph falls to at most a specified threshold \tau_{\rho} (see \cref fig:bdvd_example for an example). Figure 1: Example graph for BDVD with k=2 and \tau_{\rho}=1 . The remaining graph may only consist of connected components, each containing at most one cycle. Several subgraphs whose density exceeds \tau_{\rho} are indicated, together with a possible solution (shown as filled vertices). Note that at least one vertex of each indicated subgraph must be deleted in a solution. Here, the density of a graph is defined as the ratio of the number of edges to the number of vertices. This problem was first introduced by Bazgan et al. [ 3 ] and observed to generalize several classical vertex deletion problems: namely, Vertex Cover for \tau_{\rho}=0 , Dissociation Set for \tau_{\rho}=\nicefrac{{1}}{{2}} , and Feedback Vertex Set for \tau_{\rho}=1-\nicefrac{{1}}{{n}} (where n is the number of vertices in the graph). Moreover, for integral target densities, BDVD actually coincides with d - Orientable Deletion [ 22 ] ; this follows from a characterization of graph density by Charikar [ 8 ] . Densest subgraph problems have been studied extensively since the 1970s and have experienced renewed attention in recent years [ 27 ] . Early algorithmic approaches were based on flow techniques [ 27 , 30 , 21 ] . The aforementioned characterization for graph density by Charikar [ 8 ] is based on the dual of a linear programming approach for computing the density of a densest subgraph. This led to the notion of fractional orientations, which have since become a common tool in the study of dense subgraphs [ 4 , 7 ] . An orientation of an undirected graph G assigns a direction to each edge. A graph is called d -orientable , for d\in\mathds{N} , if there is an orientation resulting in a digraph with maximum indegree at most d 1 1 1 In parts of the literature [ 1 , 5 ] , the bound d is for the maximum outdegree. To keep consistency with the characterization by Charikar [ 8 ] , we bound the indegree, which is completely symmetrical [ 22 ] . . The task in d - Orientable Deletion is to remove a minimum number of vertices so that the resulting graph becomes d -orientable. A fractional orientation assigns parts of an edge to each endpoint. More precisely, a fractional orientation is a function \phi assigning two non-negative rationals \phi(e)^{u} and \phi(e)^{v} with \phi(e)^{u}+\phi(e)^{v}=1 to each edge e\coloneqq\{u,v\}\in E(G) . The characterization of Charikar [ 8 ] states that a densest subgraph has density \tau_{\rho} if and only if the graph admits a fractional orientation with maximum indegree \tau_{\rho} . Moreover, as observed by Bentert et al. [ 4 ] and Chandrasekaran et al. [ 7 ] , if \tau_{\rho}\in\mathds{N} , then there also exists an integral orientation 2 2 2 To avoid ambiguity between orientation and fractional orientation , we call the former integral orientation . with maximum indegree \tau_{\rho} (see \cref sec:cliquewidth for more details). Hence, d - Orientable Deletion is equivalent to BDVD with \tau_{\rho}=d . Computing an integral or fractional orientation minimizing the indegree can be done in polynomial-time via a simple reduction to flow [ 4 ] . Introduced by Asahiro et al. [ 1 ] , d - Orientable Deletion turns out to be a computationally challenging problem: It is W[2]-hard with respect to the number of vertices to remove, W[1]-hard with respect to the cliquewidth of the input graph and not approximable within a better factor than \ln n [ 22 ] . Algorithmic results include fixed-parameter tractability for treewidth and for the combined parameter cliquewidth plus d [ 5 , 22 ] . Asahiro et al. [ 2 ] provided a O(\log n) -approximation for d - Orientable Deletion . Chandrasekaran et al. [ 7 ] gave the same approximation ratio for problems generalizing BDVD . All hardness results directly carry over to BDVD . The classical computational complexity of BDVD was studied by Bazgan et al. [ 3 ] . They showed that the problem is solvable in polynomial time on trees, but is \classNP -hard on planar bipartite graphs of maximum degree 4. Unaware of the connection to d - Orientable Deletion , they reprove the \W[2] -hardness of BDVD

Read the complete text