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 language | English |
---|---|
Title of host publication | SOFSEM 2019: Theory and Practice of Computer Science |
Publisher | SPRING |
Pages | 473-289 |
Number of pages | 17 |
DOIs | |
Publication status | Published - 27 Jan 2019 |
Event | 45th International Conference on Current Trends in Theory and Practice of Computer Science - Nový Smokovec, Slovakia Duration: 27 Jan 2019 → 30 Jan 2019 https://beda.dcs.fmph.uniba.sk/sofsem2019/ |
Publication series
Name | LNCS |
---|---|
Publisher | Springer |
Volume | 11376 |
Conference
Conference | 45th International Conference on Current Trends in Theory and Practice of Computer Science |
---|---|
Abbreviated title | SOFSEM 2019 |
Country/Territory | Slovakia |
City | Nový Smokovec |
Period | 27/01/19 → 30/01/19 |
Internet address |