Algorithms and Complexity Results for the Capacitated Vertex Cover Problem

Abstract

We study the capacitated vertex cover problem (CVC). In this natural extension to the vertex cover problem, each vertex has a predefined capacity which indicates the total amount of edges that it can cover. In this paper, we study the complexity of the CVC problem. We give NP-completeness proofs for the problem on modular graphs, tree-convex graphs, and planar bipartite graphs of maximum degree three. For the first two graph classes, we prove that no subexponential-time algorithm exist for CVC unless the ETH fails.Furthermore, we introduce a series of exact exponential-time algorithms which solve the CVC problem on several graph classes in \mathcal {O}((2 - \epsilon )^n) time, for some \epsilon > 0. Amongst these graph classes are, graphs of maximum degree three, other degree-bounded graphs, regular graphs, graphs with large matchings, c-sparse graphs, and c-dense graphs. To obtain these results, we introduce an FPT treewidth algorithm which runs in \mathcal {O}^*((k + 1)^{tw}) or \mathcal {O}^*(k^k) time, where k is the solution size and tw the treewidth, improving an earlier algorithm from Dom et al.