Improved Budgeted Connected Domination and Budgeted Edge-Vertex Domination

• Published in: Theoretical computer science 2021-02, Vol.858, p.1-12
• Main Authors: Lamprou, Ioannis, Sigalas, Ioannis, Zissimopoulos, Vassilis
• Format: Article
• Language: English
• Subjects: Approximation; Budget; Connected domination; Edge-Vertex Domination; Partial
• ISSN: 0304-3975; 1879-2294
• DOI: 10.1016/j.tcs.2021.01.030

•Improved approximation algorithm for Budgeted Connected Dominating Set.•Optimal approximation algorithm for Budgeted Star Dominating Set.•Optimal approximation algorithm for Budgeted Edge-Vertex Domination. We consider the Budgeted version of the classical Connected Dominating Set problem (BCDS). Given a graph G and a budget k, we seek a connected subset of at most k vertices maximizing the number of dominated vertices in G. We improve over the previous (1−e−1)/13 state of the art [Khuller, Purohit, and Sarpatwar, SODA 2014] by introducing a new method for performing tree decompositions in the analysis of the algorithm. This new approach provides a (1−e−1)/12 approximation guarantee. By generalizing the analysis, we are able to obtain a further improvement to (1−e−7/8)/11. On the other hand, we prove a (1−e−1+ϵ) inapproximability bound, for any ϵ>0, holding also if the subset is required to have a star as a subgraph. In the latter case, we design another algorithm with a matching (1−e−1) approximation guarantee. Also, we examine the edge-vertex domination variant, where an edge dominates its endpoints and all vertices neighboring them. In Budgeted Edge-Vertex Domination (BEVD), we seek a (not necessarily connected) subset of k edges maximizing the number of dominated vertices in G. We prove a (1−e−1)-approximation and a (1−e−1+ϵ)-inapproximability by reductions to/from the maximum coverage problem. Finally, we study the “dual” Partial Edge-Vertex Domination (PEVD) problem, and we present a log-approximation by a reduction to the partial cover problem.