New fixed-parameter algorithms improve vertex deletion under density limits
Bounded-Density Vertex Deletion Beyond Vertex Cover
Data Structures and Algorithms
Summary
This paper studies a problem about removing a limited number of points (vertices) from a network so that the remaining pieces are not too connected, measured by density. The authors solve open cases by showing when this is computationally feasible based on certain network structures, like twin-cover and distance to cluster. They also clarify that for some combinations of parameters, the problem remains computationally hard. Their work helps understand exactly when such network simplifications can be efficiently computed.
What this means in practice
- •For network analysts: Identify network simplifications that keep subnetwork connections below a threshold when certain structural parameters are small.
- •For graph algorithm engineers: Develop efficient algorithms for vertex deletion problems restricted by twin-cover or distance-to-cluster parameters to control graph density.
A theory result. No direct application yet.
Authors
Adrian Miclăuş, Alexandru Popa, Andrei Popa
Abstract
We study \textsc{Bounded-Density Vertex Deletion} (BDVD), where one asks whether at most \(k\) vertices can be deleted so that every remaining subgraph has density at most a rational input threshold \(τ_ρ\). We address the twin-cover and distance-to-cluster cases left open by Raupach, Breitkopf, Herrmann, and Nichterlein (MFCS 2026). We prove fixed-parameter tractability parameterized solely by the twin-cover number, for unrestricted input density. For distance to cluster, we establish fixed-parameter tractability parameterized by \(\operatorname{dc}(G)+\lfloor2τ_ρ+1\rfloor\), and complement this with \(\mathsf{W[1]}\)-hardness parameterized by \(\operatorname{dc}(G)\) alone when the target density is part of the input, even for integral targets. Thus distance to cluster alone is fixed-parameter tractable throughout \(τ_ρ<1\), while it is insufficient for unrestricted input density. Finally, we settle the combined parameter treewidth plus solution size, an open problem posed by Bazgan, Nichterlein, and Vazquez Alferez (JCSS 2025). We prove that BDVD is \(\mathsf{W[1]}\)-hard parameterized by \(\operatorname{td}(G)+k\), and hence also by \(\operatorname{tw}(G)+k\), already for targets strictly between \(1\) and \(2\).