Parameterized Capacitated Vertex Cover Revisited

arXiv:2604.18746v1 Announce Type: new
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$…