Improved Budgeted Connected Domination and 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 [Formula: see text] 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 [Formula: see text] 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 [Formula: see text]. On the other hand, we prove a [Formula: see text] inapproximability bound, for any [Formula: see text]. 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 [Formula: see text]-approximation algorithm. Also, for any [Formula: see text], we present a [Formula: see text]-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 [Formula: see text] are given. The goal is to select a minimum-size set of edges to dominate at least [Formula: see text] vertices in G. In this case, we present a [Formula: see text]-approximation algorithm by a reduction to the partial cover problem.