Algorithms and Complexity Results for the Capacitated Vertex Cover Problem

J.M.M. van Rooij, Sebastiaan B. van Rooij

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

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.
Original languageEnglish
Title of host publicationSOFSEM 2019: Theory and Practice of Computer Science
PublisherSPRING
Pages473-289
Number of pages17
DOIs
Publication statusPublished - 27 Jan 2019
Event45th International Conference on Current Trends in Theory and Practice of Computer Science - Nový Smokovec, Slovakia
Duration: 27 Jan 201930 Jan 2019
https://beda.dcs.fmph.uniba.sk/sofsem2019/

Publication series

NameLNCS
PublisherSpringer
Volume11376

Conference

Conference45th International Conference on Current Trends in Theory and Practice of Computer Science
Abbreviated titleSOFSEM 2019
Country/TerritorySlovakia
CityNový Smokovec
Period27/01/1930/01/19
Internet address

Fingerprint

Dive into the research topics of 'Algorithms and Complexity Results for the Capacitated Vertex Cover Problem'. Together they form a unique fingerprint.

Cite this