pith. sign in

arxiv: 2606.26012 · v1 · pith:GF2E7BPCnew · submitted 2026-06-24 · 💻 cs.DS

On the Parameterized Complexity of Bounded-Density Vertex Deletion

Jakob Raupach , Tom-Lukas Breitkopf , Anton Herrmann , Andr\'e Nichterlein This is my paper

Pith reviewed 2026-06-25 19:18 UTC · model grok-4.3

classification 💻 cs.DS
keywords parameterized complexityvertex deletionbounded densitytreewidthW[1]-hardnesstreedepthfeedback vertex setcliquewidth
0
0 comments X

The pith

Bounded Density Vertex Deletion is W[1]-hard parameterized by treewidth but FPT for max leaf number and vertex integrity.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies deleting at most k vertices from a graph so its densest subgraph has density at most a target value τ_ρ. It answers an open question by proving the problem is W[1]-hard when parameterized by treewidth, shown via hardness for the smaller parameters treedepth and feedback vertex number. It gives matching positive results: the problem is fixed-parameter tractable for the larger parameters max leaf number and vertex integrity. When the target density τ_ρ is treated as a fixed constant, the problem is FPT even for the parameter cliquewidth. Together these results draw a sharp line between tractable and intractable regimes under structural parameterizations.

Core claim

We resolve the open question on the parameterized complexity of Bounded Density Vertex Deletion with respect to treewidth by showing W[1]-hardness with respect to treedepth and feedback vertex number, which imply the same for treewidth. We obtain positive FPT results for the larger parameters max leaf number and vertex integrity. Under the assumption that the target density τ_ρ is a fixed constant, the problem is FPT even for cliquewidth.

What carries the argument

W[1]-hardness reductions from known hard problems that preserve both the density threshold τ_ρ and the deletion budget k across the constructed instances.

If this is right

  • BDVD admits no FPT algorithm parameterized by treewidth unless FPT equals W[1].
  • BDVD admits an FPT algorithm when parameterized by max leaf number.
  • BDVD admits an FPT algorithm when parameterized by vertex integrity.
  • When τ_ρ is a fixed constant, BDVD admits an FPT algorithm parameterized by cliquewidth.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The separation between hardness for treewidth and tractability for cliquewidth under constant τ_ρ may indicate that density constraints behave differently from connectivity constraints under modular decompositions.
  • Similar parameterized complexity results may hold for other deletion problems whose objective is to bound a global density measure rather than a local connectivity measure.
  • The FPT algorithms for vertex integrity could be lifted to deletion problems whose objective combines density with other subgraph properties.

Load-bearing premise

The W[1]-hardness reductions correctly preserve the density threshold τ_ρ and the budget k in the constructed instances.

What would settle it

An explicit FPT algorithm for BDVD parameterized by treewidth, or a concrete instance produced by the treedepth reduction in which the densest subgraph density exceeds τ_ρ after the claimed deletions.

read the original abstract

We explore the parameterized complexity of Bounded Density Vertex Deletion (BDVD): given a graph $G$, an integer budget $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$ can be reduced to at most $\tau_\rho$ by deleting at most $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]-hardness with respect to various parameters, including treedepth and feedback vertex number. These results imply 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 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The manuscript studies the parameterized complexity of Bounded-Density Vertex Deletion (BDVD): delete at most k vertices so that the densest subgraph has density at most a given threshold τ_ρ. It claims to resolve the open question left by Bazgan et al. on treewidth by proving W[1]-hardness for treedepth and feedback vertex number (which the authors state imply W[1]-hardness for treewidth), while also establishing FPT membership for larger parameters (max leaf number, vertex integrity) and, when τ_ρ is constant, for cliquewidth.

Significance. If the technical results are correct, the paper supplies a refined map of tractable versus intractable regimes for BDVD under structural parameters, separating parameters below and above treewidth and clarifying the effect of fixing the density threshold.

major comments (1)
  1. [Abstract] Abstract: the assertion that W[1]-hardness results for treedepth and feedback vertex number 'imply W[1]-hardness with respect to treewidth' is incorrect for treedepth. Hardness parameterized by feedback vertex number transfers because tw(G) ≤ fvs(G)+1, so an FPT algorithm for treewidth would yield an FPT algorithm for feedback vertex number. The converse direction fails for treedepth: tw(G) ≤ td(G), yet there exist families with bounded treewidth and unbounded treedepth (paths, complete binary trees). Consequently a reduction establishing no f(td)·n^O(1) algorithm need not produce instances of bounded treewidth, and the claimed resolution of the treewidth question does not follow from the treedepth result.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for identifying the inaccuracy in our abstract regarding the transfer of hardness results. We agree with the analysis and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the assertion that W[1]-hardness results for treedepth and feedback vertex number 'imply W[1]-hardness with respect to treewidth' is incorrect for treedepth. Hardness parameterized by feedback vertex number transfers because tw(G) ≤ fvs(G)+1, so an FPT algorithm for treewidth would yield an FPT algorithm for feedback vertex number. The converse direction fails for treedepth: tw(G) ≤ td(G), yet there exist families with bounded treewidth and unbounded treedepth (paths, complete binary trees). Consequently a reduction establishing no f(td)·n^O(1) algorithm need not produce instances of bounded treewidth, and the claimed resolution of the treewidth question does not follow from the treedepth result.

    Authors: We appreciate the referee's clarification. We agree that W[1]-hardness parameterized by treedepth does not imply W[1]-hardness parameterized by treewidth, because a reduction establishing hardness for treedepth need not produce instances whose treewidth is bounded by a function of the original parameter. However, the W[1]-hardness result for feedback vertex number does transfer, since tw(G) ≤ fvs(G) + 1 and thus an FPT algorithm for treewidth would immediately yield one for feedback vertex number. Our FVS result therefore resolves the open question of Bazgan et al. We will revise the abstract to remove the incorrect claim about the treedepth result implying the treewidth result and to state clearly that the feedback vertex number hardness implies W[1]-hardness for treewidth. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper establishes W[1]-hardness for BDVD via FPT reductions from known W[1]-hard problems (parameterized by treedepth and feedback vertex number) and gives direct FPT algorithms (dynamic programming) for larger parameters such as max leaf number and vertex integrity. The statement that these imply W[1]-hardness for treewidth follows from the independent inequalities tw(G) ≤ td(G) and tw(G) ≤ fvs(G) + 1; the same reductions remain FPT reductions under the smaller parameter. No quantity is defined in terms of another, no parameter is fitted and then renamed as a prediction, and no load-bearing step relies on a self-citation chain. The derivation is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Results rest on the standard definitions of W[1]-hardness via fpt-reductions and FPT membership via dynamic programming or kernelization; no free parameters, invented entities, or ad-hoc axioms beyond textbook parameterized complexity are introduced.

axioms (2)
  • standard math W[1]-hardness is witnessed by an fpt-reduction from a known W[1]-hard problem that preserves the parameter and the density threshold
    Invoked when stating the treedepth and feedback vertex number hardness results.
  • standard math FPT membership follows from standard techniques such as dynamic programming on tree decompositions or bounded-height search trees when the parameter admits them
    Used for the positive results on max leaf number, vertex integrity, and constant-τ_ρ cliquewidth.

pith-pipeline@v0.9.1-grok · 5796 in / 1445 out tokens · 27299 ms · 2026-06-25T19:18:49.046688+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

34 extracted references · 1 canonical work pages

  1. [1]

    Destroying densest subgraphs is hard , journal =

    Cristina Bazgan and André Nichterlein and Sofia. Destroying densest subgraphs is hard , journal =. 2025 , issn_IGNORE =

    2025

  2. [2]

    1984 , publisher =

    Finding a maximum density subgraph , author =. 1984 , publisher =

    1984

  3. [3]

    2019 , url =

    Generalized Feedback Vertex Set Problems on Bounded-Treewidth Graphs: Chordality is the Key to Single-Exponential Parameterized Algorithms , journal =. 2019 , url =. doi:10.1007/S00453-019-00579-4 , timestamp =

    work page doi:10.1007/s00453-019-00579-4 2019

  4. [4]

    Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization (

    Moses Charikar , title =. Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization (. 2000 , url =

    2000

  5. [5]

    and Kowalik, Lukasz and Lokshtanov, Daniel and Marx, Daniel and Pilipczuk, Marcin and Pilipczuk, Michal and Saurabh, Saket , title =

    Cygan, Marek and Fomin, Fedor V. and Kowalik, Lukasz and Lokshtanov, Daniel and Marx, Daniel and Pilipczuk, Marcin and Pilipczuk, Michal and Saurabh, Saket , title =. 2015 , isbn =

    2015

  6. [6]

    Downey and Michael R

    Rodney G. Downey and Michael R. Fellows , title =. 2013 , url =

    2013

  7. [7]

    Proceedings of the 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024) , series =

    Hanaka, Tesshu and Lampis, Michael and Vasilakis, Manolis and Yoshiwatari, Kanae , title =. Proceedings of the 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024) , series =. 2024 , volume_IGNORE =

    2024

  8. [8]

    ACM Computing Surveys , month = apr, articleno =

    Lanciano, Tommaso and Miyauchi, Atsushi and Fazzone, Adriano and Bonchi, Francesco , title =. ACM Computing Surveys , month = apr, articleno =. 2024 , issue_date =

    2024

  9. [9]

    Proceedings of the 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) , series =

    Chandrasekaran, Karthekeyan and Chekuri, Chandra and Kulkarni, Shubhang , title =. Proceedings of the 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) , series =. 2025 , volume_IGNORE =

    2025

  10. [10]

    , title =

    Brandstädt, Andreas and Le, Van Bang and Spinrad, Jeremy P. , title =. 1999 , doi =

    1999

  11. [11]

    2014 , publisher=

    Sparsity: graphs, structures, and algorithms , author=. 2014 , publisher=

    2014

  12. [12]

    Representation of a finite graph by a set of intervals on the real line , url =

    Lekkeikerker, Cornelis and Boland, Johan , journal =. Representation of a finite graph by a set of intervals on the real line , url =

  13. [13]

    Density Matters:

    Matthias Bentert and Tom. Density Matters:. Proceedings of the 43rd International Symposium on Theoretical Aspects of Computer Science (. 2026 , url =

    2026

  14. [14]

    M. R. Garey and David S. Johnson , title =. 1979 , isbn =

    1979

  15. [15]

    On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem , volume =

    Ganian, Robert and Klute, Fabian and Ordyniak, Sebastian , journal =. On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem , volume =. 2021 , url =

    2021

  16. [16]

    Journal of Graph Algorithms and Applications , volume =

    Yuichi Asahiro and Jesper Jansson and Eiji Miyano and Hirotaka Ono , title =. Journal of Graph Algorithms and Applications , volume =. 2015 , url =

    2015

  17. [17]

    Bodlaender and Hirotaka Ono and Yota Otachi , title =

    Hans L. Bodlaender and Hirotaka Ono and Yota Otachi , title =. Algorithmica , volume =. 2018 , url =

    2018

  18. [18]

    Algorithmica , volume =

    Tesshu Hanaka and Ioannis Katsikarelis and Michael Lampis and Yota Otachi and Florian Sikora , title =. Algorithmica , volume =. 2020 , url =

    2020

  19. [19]

    A network flow solution to some nonlinear 0-1 programming problems, with applications to graph theory , volume =

    Jean. A network flow solution to some nonlinear 0-1 programming problems, with applications to graph theory , volume =. Networks , number =. 1982 , url =

    1982

  20. [20]

    , institution =

    Goldberg, Andrew V. , institution =. Finding a Maximum Density Subgraph , year =

  21. [21]

    Theory of Computing Systems , volume =

    Yuichi Asahiro and Jesper Jansson and Eiji Miyano and Hirotaka Ono , title =. Theory of Computing Systems , volume =. 2016 , url =

    2016

  22. [22]

    Almost-Linear Time Parameterized Algorithm for Rankwidth via Dynamic Rankwidth , booktitle =

    Tuukka Korhonen and Marek Sokolowski , editor =. Almost-Linear Time Parameterized Algorithm for Rankwidth via Dynamic Rankwidth , booktitle =. 2024 , url =

    2024

  23. [23]

    Makowsky and Udi Rotics , title =

    Bruno Courcelle and Johann A. Makowsky and Udi Rotics , title =. Theory of Computing Systems , volume =. 2000 , url =

    2000

  24. [24]

    Theoretical Computer Science , volume =

    Tatsuya Gima and Tesshu Hanaka and Masashi Kiyomi and Yasuaki Kobayashi and Yota Otachi , title =. Theoretical Computer Science , volume =. 2022 , url =

    2022

  25. [25]

    On the Computational Complexity of Vertex Integrity and Component Order Connectivity , journal =

    P. On the Computational Complexity of Vertex Integrity and Component Order Connectivity , journal =. 2016 , url =

    2016

  26. [26]

    An application of simultaneous Diophantine approximation in combinatorial optimization , journal =

    Andr. An application of simultaneous Diophantine approximation in combinatorial optimization , journal =. 1987 , url =

    1987

  27. [27]

    Mathematics of Operations Research , volume =

    Ravi Kannan , title =. Mathematics of Operations Research , volume =. 1987 , url =

    1987

  28. [28]

    Lenstra Jr

    Hendrik W. Lenstra Jr. , title =. Mathematics of Operations Research , volume =. 1983 , url =

    1983

  29. [29]

    Graph Classes: a Survey , publisher =

    Andreas Brandst. Graph Classes: a Survey , publisher =

  30. [30]

    Modularity Clustering Parameterized by Max Leaf Number , booktitle =

    Jaroslav Garvardt and Christian Komusiewicz , editor =. Modularity Clustering Parameterized by Max Leaf Number , booktitle =. 2024 , url =

    2024

  31. [31]

    Journal of Graph Algorithms and Applications , volume =

    David Eppstein , title =. Journal of Graph Algorithms and Applications , volume =. 2015 , url =

    2015

  32. [32]

    Corneil and Udi Rotics , title =

    Derek G. Corneil and Udi Rotics , title =. 2005 , url =

    2005

  33. [33]

    Bruno Courcelle and Stephan Olariu , title =. Discret. Appl. Math. , volume =. 2000 , url =

    2000

  34. [34]

    Fellows and Jiong Guo and Iyad A

    Rosa Enciso and Michael R. Fellows and Jiong Guo and Iyad A. Kanj and Frances A. Rosamond and Ondrej Such. What Makes Equitable Connected Partition Easy , booktitle =. 2009 , address_IGNORE =

    2009