{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreia3vpgczzfnlq2kzdsnr5turody4inqdvwml7ktjul4zteemzumcu",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mk2ql44acwh2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2604.18746v1",
  "publishedAt": "2026-04-22T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Michael Lampis",
    "Manolis Vasilakis"
  ],
  "textContent": "**Authors:** Michael Lampis, Manolis Vasilakis\n\nCapacitated 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$...",
  "title": "Parameterized Capacitated Vertex Cover Revisited"
}