pith. sign in

arxiv: 2604.18746 · v1 · submitted 2026-04-20 · 💻 cs.DS · cs.CC

Parameterized Capacitated Vertex Cover Revisited

Michael Lampis , Manolis Vasilakis This is my paper

Pith reviewed 2026-05-10 03:04 UTC · model grok-4.3

classification 💻 cs.DS cs.CC
keywords Capacitated Vertex CoverParameterized ComplexityExponential Time HypothesisTreewidthVertex IntegrityFine-grained ComplexityN-fold Integer ProgrammingClique-width
0
0 comments X

The pith

Capacitated Vertex Cover has no k^{o(k)} n^{O(1)} algorithm under the Exponential Time Hypothesis.

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

The paper studies the exact complexity of Capacitated Vertex Cover, where vertices have capacities that limit the edges they can cover. For the solution-size parameter k it shows that, assuming the Exponential Time Hypothesis, every algorithm needs time at least k to a power that grows linearly with k. This immediately implies that all known treewidth-based algorithms are optimal even when the graph has small tree-depth. The work also supplies matching upper bounds for the vertex-integrity parameter and hardness results for clique-width and vertex-cover number.

Core claim

Under the Exponential Time Hypothesis there is no algorithm for Capacitated Vertex Cover running in k^{o(k)} n^{O(1)} time. The same lower bound holds when the parameter is tree-depth instead of treewidth. For vertex integrity an algorithm with running time vi^{O(vi^2)} n^{O(1)} is obtained via N-fold integer programming, improving the previous double-exponential dependence.

What carries the argument

Parameter-preserving reductions from 3-SAT that keep both the solution size k and treewidth (or tree-depth) small, combined with dynamic programming over tree decompositions and N-fold integer programming for the vertex-integrity upper bound.

If this is right

  • Existing k^{O(tw)} algorithms for treewidth are asymptotically optimal.
  • The same optimality extends to the stronger tree-depth parameter.
  • A 2^{O(vc^{2-ε})} algorithm for vertex-cover number would yield faster algorithms for a wider class of integer programs.
  • The problem remains NP-hard on graphs of linear clique-width 6.

Where Pith is reading between the lines

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

  • Capacitated covering problems appear to require qualitatively higher parameterized time than their uncapacitated counterparts.
  • The vertex-integrity result suggests that N-fold integer programming may be a general route to single-exponential algorithms for capacitated problems on graphs with small vertex integrity.

Load-bearing premise

The Exponential Time Hypothesis is true and the reductions preserve the parameters k and treewidth without super-polynomial blow-up.

What would settle it

An explicit algorithm that solves every instance of Capacitated Vertex Cover in time k^{o(k)} n^{O(1)} would falsify the ETH-based lower bound.

read the original abstract

Capacitated Vertex Cover is the hard-capacitated variant of Vertex Cover: given a graph, a capacity for every vertex, and an integer $k$, the task is to select at most $k$ vertices that cover all edges and assign each edge to one of its chosen endpoints so that no chosen vertex receives more incident edges than its capacity. This problem is a classical benchmark in parameterized complexity, as it was among the first natural problems shown to be W[1]-hard when parameterized by treewidth. We revisit its exact complexity from a fine-grained parameterized perspective and obtain a much sharper picture for several standard parameters. For the natural parameter $k$, we prove under the Exponential Time Hypothesis (ETH) that no algorithm with running time $k^{o(k)} n^{\mathcal{O}(1)}$ exists. In particular, this shows that the known algorithms with running time $k^{\mathcal{O}(\mathrm{tw})} n^{\mathcal{O}(1)}$ are essentially optimal. We then turn to more general structural parameters. For vertex cover number $\mathrm{vc}$, we give evidence against a $2^{\mathcal{O}(\mathrm{vc}^{2-\varepsilon})} n^{\mathcal{O}(1)}$ algorithm, as such an improvement would imply corresponding progress for a broader class of integer-programming-type problems. We complement this barrier with a nearly matching upper bound for vertex integrity $\mathrm{vi}$, improving the previously known double-exponential dependence to an algorithm with running time $\mathrm{vi}^{\mathcal{O}(\mathrm{vi}^{2})} n^{\mathcal{O}(1)}$ using $N$-fold integer programming. For treewidth, we show that the standard dynamic programming algorithm with running time $n^{\mathcal{O}(\mathrm{tw})}$ is essentially optimal under the ETH, even if one parameterizes by tree-depth. Turning to clique-width, we prove that Capacitated Vertex Cover remains NP-hard already on graphs of linear clique-width $6$...

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

2 major / 2 minor

Summary. The manuscript revisits Capacitated Vertex Cover from a fine-grained parameterized perspective. It proves under ETH that no k^{o(k)} n^{O(1)}-time algorithm exists for the natural parameter k, claiming this establishes essential optimality of known k^{O(tw)} n^{O(1)} algorithms. It further provides evidence against 2^{O(vc^{2-ε})} algorithms for vertex cover number, a vi^{O(vi^2)} n^{O(1)} algorithm via N-fold IP for vertex integrity, an ETH-based optimality proof for the n^{O(tw)} DP even under tree-depth parameterization, and NP-hardness on linear clique-width 6 graphs.

Significance. If the lower-bound reductions are parameter-preserving as stated, the results deliver a sharper complexity map for this benchmark problem, including a concrete link between the natural parameter and structural parameters, plus a technical improvement via N-fold integer programming. The ETH-based claims, if fully verified, would be a solid contribution to fine-grained parameterized complexity.

major comments (2)
  1. [Abstract and ETH lower-bound section for parameter k] Abstract (final sentence of the k-parameter paragraph): The claim that the k^{o(k)} lower bound shows k^{O(tw)} algorithms are 'essentially optimal' is load-bearing for the paper's narrative. This transfer requires the reduction to output graphs with tw = Ω(k); the manuscript must explicitly bound the treewidth of the constructed instances in terms of the source parameter (see also the reduction in the section establishing the ETH lower bound for k).
  2. [Treewidth and tree-depth lower-bound section] Treewidth paragraph: The statement that the standard n^{O(tw)} DP is 'essentially optimal under the ETH, even if one parameterizes by tree-depth' requires the reduction to relate tree-depth to treewidth such that a hypothetical n^{o(tw)} algorithm would be contradicted. The exact dependence of tree-depth on the source parameter in the construction must be stated and verified.
minor comments (2)
  1. [Notation and vertex-integrity section] Ensure all running-time expressions consistently use mathrm for tw, vc, vi, etc., and that the N-fold IP running time derivation is cross-referenced to the specific theorem on vertex integrity.
  2. [Abstract] The abstract mentions 'a broader class of integer-programming-type problems' for the vc barrier; add a brief pointer to the relevant prior work on those problems.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. We address each major comment below. We agree that the explicit parameter relationships in the reductions must be stated and will revise the manuscript to include them.

read point-by-point responses

  1. Referee: [Abstract and ETH lower-bound section for parameter k] Abstract (final sentence of the k-parameter paragraph): The claim that the k^{o(k)} lower bound shows k^{O(tw)} algorithms are 'essentially optimal' is load-bearing for the paper's narrative. This transfer requires the reduction to output graphs with tw = Ω(k); the manuscript must explicitly bound the treewidth of the constructed instances in terms of the source parameter (see also the reduction in the section establishing the ETH lower bound for k).

    Authors: We thank the referee for highlighting this point. The reduction establishing the ETH lower bound for parameter k produces instances with treewidth Θ(k). This follows from the gadget construction, where the treewidth is linear in the source parameter (which is set to Θ(k)). Thus, an algorithm running in k^{o(tw)} n^{O(1)} time on these instances would yield a k^{o(k)} n^{O(1)} algorithm, contradicting the lower bound. We will add an explicit statement of the bound tw = Θ(k) to the abstract and the ETH lower-bound section. revision: yes

  2. Referee: [Treewidth and tree-depth lower-bound section] Treewidth paragraph: The statement that the standard n^{O(tw)} DP is 'essentially optimal under the ETH, even if one parameterizes by tree-depth' requires the reduction to relate tree-depth to treewidth such that a hypothetical n^{o(tw)} algorithm would be contradicted. The exact dependence of tree-depth on the source parameter in the construction must be stated and verified.

    Authors: We agree that the dependence requires explicit statement. Our reduction yields instances where tree-depth td = O(tw) and tw = Ω(s) for the source parameter s from the ETH-hard problem. This ensures that a hypothetical n^{o(tw)} algorithm would imply an n^{o(td)} algorithm on the constructed instances (with td linear in the source parameter), which is ruled out by the ETH lower bound. We will add the precise relation td = O(tw) with the corresponding verification in the revised treewidth and tree-depth section. revision: yes

Circularity Check

0 steps flagged

No significant circularity; claims rest on external ETH and standard techniques

full rationale

The paper derives its ETH-based lower bound of no k^{o(k)} n^{O(1)} algorithm via reduction from an external hypothesis (ETH), with no evidence that the reduction or the optimality transfer to k^{O(tw)} algorithms is self-definitional, fitted by construction, or dependent on a load-bearing self-citation chain. Upper bounds rely on established dynamic programming over treewidth and N-fold integer programming, which are independent of the paper's fitted values or prior self-references. No quoted steps reduce the claimed results to the inputs by definition or via ansatz smuggling. The derivation is self-contained against external benchmarks, yielding only a minor self-citation risk at most.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Central claims rest on the ETH assumption for all lower bounds and on the correctness of N-fold integer programming for the vertex-integrity upper bound; no free parameters or invented entities are introduced.

axioms (2)
  • domain assumption Exponential Time Hypothesis (ETH)
    Invoked to obtain the k^{o(k)} and n^{O(tw)} lower bounds.
  • standard math Correctness of N-fold integer programming algorithms
    Used to obtain the vi^{O(vi^2)} upper bound.

pith-pipeline@v0.9.0 · 5653 in / 1315 out tokens · 52510 ms · 2026-05-10T03:04:07.997291+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

38 extracted references · 38 canonical work pages

  1. [1]

    Diestel, Graph Theory, Graduate Texts in Mathematics (Springer Berlin Heidelberg, ed

    Reinhard Diestel , title =. 2025 , series =. doi:10.1007/978-3-662-70107-2 , isbn =

    work page doi:10.1007/978-3-662-70107-2 2025

  2. [2]

    Fomin and Lukasz Kowalik and Daniel Lokshtanov and D

    Marek Cygan and Fedor V. Fomin and Lukasz Kowalik and Daniel Lokshtanov and D. Parameterized Algorithms , publisher =. 2015 , doi =

    work page 2015

  3. [3]

    2024 , doi =

    Michael Lampis and Manolis Vasilakis , title =. 2024 , doi =

    work page 2024

  4. [4]

    Parameterized and Exact Computation, Third International Workshop,

    Michael Dom and Daniel Lokshtanov and Saket Saurabh and Yngve Villanger , title =. Parameterized and Exact Computation, Third International Workshop,. 2008 , doi =

    work page 2008

  5. [5]

    Bodlaender and Carla Groenland and Hugo Jacob and Lars Jaffke and Paloma T

    Hans L. Bodlaender and Carla Groenland and Hugo Jacob and Lars Jaffke and Paloma T. Lima , title =. Algorithmica , volume =. 2025 , doi =

    work page 2025

  6. [6]

    Tatsuya Gima and Tesshu Hanaka and Masashi Kiyomi and Yasuaki Kobayashi and Yota Otachi , title =. Theor. Comput. Sci. , volume =. 2022 , doi =

    work page 2022

  7. [7]

    Automata, Languages, and Programming - 41st International Colloquium,

    Michael Lampis , title =. Automata, Languages, and Programming - 41st International Colloquium,. 2014 , doi =

    work page 2014

  8. [8]

    Theory Comput

    Jiong Guo and Rolf Niedermeier and Sebastian Wernicke , title =. Theory Comput. Syst. , volume =. 2007 , doi =

    work page 2007

  9. [9]

    34th International Symposium on Algorithms and Computation,

    Huairui Chu and Bingkai Lin , title =. 34th International Symposium on Algorithms and Computation,. 2023 , doi =

    work page 2023

  10. [10]

    Proceedings of the 2025 Annual

    Daniel Lokshtanov and Abhishek Sahu and Saket Saurabh and Vaishali Surianarayanan and Jie Xue , title =. Proceedings of the 2025 Annual. 2025 , doi =

    work page 2025

  11. [11]

    van Rooij and Johan M

    Sebastiaan B. van Rooij and Johan M. M. van Rooij , title =. 2019 , doi =

    work page 2019

  12. [12]

    Bodlaender and Carla Groenland and Hugo Jacob and Marcin Pilipczuk and Michal Pilipczuk , title =

    Hans L. Bodlaender and Carla Groenland and Hugo Jacob and Marcin Pilipczuk and Michal Pilipczuk , title =. 17th International Symposium on Parameterized and Exact Computation,. 2022 , doi =

    work page 2022

  13. [13]

    Bodlaender and Krisztina Szil

    Hans L. Bodlaender and Krisztina Szil. Discret. Appl. Math. , volume =. 2026 , doi =

    work page 2026

  14. [14]

    Approximation and Online Algorithms - 15th International Workshop,

    Amariah Becker , title =. Approximation and Online Algorithms - 15th International Workshop,. 2017 , doi =

    work page 2017

  15. [15]

    16th Innovations in Theoretical Computer Science Conference,

    Lars Rohwedder and Karol Wegrzycki , title =. 16th Innovations in Theoretical Computer Science Conference,. 2025 , doi =

    work page 2025

  16. [16]

    On a Combinatorial Problem in Number Theory , journal =

    Bernt Lindstr. On a Combinatorial Problem in Number Theory , journal =. 1965 , doi =

    work page 1965

  17. [17]

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

    work page 1979

  18. [18]

    Grundy Distinguishes Treewidth from Pathwidth , journal =

    R. Grundy Distinguishes Treewidth from Pathwidth , journal =. 2022 , doi =

    work page 2022

  19. [19]

    Lenstra Jr

    Hendrik W. Lenstra Jr. , title =. Math. Oper. Res. , volume =. 1983 , doi =

    work page 1983

  20. [20]

    Sudipto Guha and Refael Hassin and Samir Khuller and Einat Or , title =. J. Algorithms , volume =. 2003 , doi =

    work page 2003

  21. [21]

    2019 , doi =

    Marthe Bonamy and Lukasz Kowalik and Michal Pilipczuk and Arkadiusz Socala and Marcin Wrochna , title =. 2019 , doi =

    work page 2019

  22. [22]

    Approximation of Partial Capacitated Vertex Cover , journal =

    Reuven Bar. Approximation of Partial Capacitated Vertex Cover , journal =. 2010 , doi =

    work page 2010

  23. [23]

    A Primal-Dual Bicriteria Distributed Algorithm for Capacitated Vertex Cover , journal =

    Fabrizio Grandoni and Jochen K. A Primal-Dual Bicriteria Distributed Algorithm for Capacitated Vertex Cover , journal =. 2008 , doi =

    work page 2008

  24. [24]

    2006 , doi =

    Julia Chuzhoy and Joseph Naor , title =. 2006 , doi =

    work page 2006

  25. [25]

    Rajiv Gandhi and Eran Halperin and Samir Khuller and Guy Kortsarz and Aravind Srinivasan , title =. J. Comput. Syst. Sci. , volume =. 2006 , doi =

    work page 2006

  26. [26]

    Iterative Partial Rounding for Vertex Cover with Hard Capacities , journal =

    Mong. Iterative Partial Rounding for Vertex Cover with Hard Capacities , journal =. 2021 , doi =

    work page 2021

  27. [27]

    Tight Algorithms for Vertex Cover with Hard Capacities on Multigraphs and Hypergraphs , booktitle =

    Sam Chiu. Tight Algorithms for Vertex Cover with Hard Capacities on Multigraphs and Hypergraphs , booktitle =. 2017 , doi =

    work page 2017

  28. [28]

    Tight approximation for partial vertex cover with hard capacities , journal =

    Mong. Tight approximation for partial vertex cover with hard capacities , journal =. 2019 , doi =

    work page 2019

  29. [29]

    2022 , doi =

    Robert Ganian and Eun Jung Kim and Stefan Szeider , title =. 2022 , doi =

    work page 2022

  30. [30]

    Goemans and Sam Chiu

    Wang Chi Cheung and Michel X. Goemans and Sam Chiu. Improved Algorithms for Vertex Cover with Hard Capacities on Multigraphs and Hypergraphs , booktitle =. 2014 , doi =

    work page 2014

  31. [31]

    Klaus Jansen and Petra Scheffler , title =. Discret. Appl. Math. , volume =. 1997 , doi =

    work page 1997

  32. [32]

    Defective Coloring on Classes of Perfect Graphs , journal =

    R. Defective Coloring on Classes of Perfect Graphs , journal =. 2022 , doi =

    work page 2022

  33. [33]

    Proceedings of the 2025 Annual

    Michael Lampis , title =. Proceedings of the 2025 Annual. 2025 , doi =

    work page 2025

  34. [34]

    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 , doi =

    work page 2016

  35. [35]

    An algorithmic theory of integer programming.arXiv preprint arXiv:1904.01361, 2019

    Friedrich Eisenbrand and Christoph Hunkenschr. An Algorithmic Theory of Integer Programming , year =. 1904.01361 , archivePrefix=

    work page arXiv 1904

  36. [36]

    2025 , eprint =

    Dusan Knop and Nikolaos Melissinos and Manolis Vasilakis , title =. 2025 , eprint =

    work page 2025

  37. [37]

    Equitable Connected Partition and Structural Parameters Revisited: N-Fold Beats

    V. Equitable Connected Partition and Structural Parameters Revisited: N-Fold Beats. 49th International Symposium on Mathematical Foundations of Computer Science,. 2024 , doi =

    work page 2024

  38. [38]

    Integer programming in parameterized complexity: Five miniatures , journal =

    Tomas Gavenciak and Martin Kouteck. Integer programming in parameterized complexity: Five miniatures , journal =. 2022 , doi =

    work page 2022