2019/07/15 by Ioannis Lamprou, Lamprou, Ioannis, Ioannis Sigalas +3 · 1 citation
Computer Science · Economics, Econometrics and Finance · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Game Theory and Voting Systems
paper · pdf · doi:10.48550/arxiv.1907.06576
openalex publication_date 2019/07/15 · openalex created_date 2022/07/28 · openalex updated_date 2026/07/28
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-1/e)/13 approximation in [Khuller, Purohit, and Sarpatwar, SODA 2014] by introducing a new method for performing tree decompositions in the analysis of the last part of the algorithm. This new approach provides a (1-1/e)/12 approximation guarantee. By generalizing the analysis of the first part of the algorithm, we are able to modify it appropriately and obtain a further improvement to (1-e-7/8)/11. On the other hand, we prove a (1-1/e+ε) inapproximability bound, for any ε> 0. We also examine the edge-vertex domination variant, where an edge dominates its endpoints and all vertices neighboring them. In Budgeted Edge-Vertex Domination (BEVD), we are given a graph G, and a budget k, and we seek a, not necessarily connected, subset of k edges such that the number of dominated vertices in G is maximized. We prove there exists a (1-1/e)-approximation algorithm. Also, for any ε> 0, we present a (1-1/e+ε)-inapproximability result by a gap-preserving reduction from the maximum coverage problem. Finally, we examine the "dual" Partial Edge-Vertex Domination (PEVD) problem, where a graph G and a quota n' are given. The goal is to select a minimum-size set of edges to dominate at least n' vertices in G. In this case, we present a H(n')-approximation algorithm by a reduction to the partial cover problem.