TY - JOUR
T1 - Analyzing the optimal neighborhood
T2 - Algorithms for partial and budgeted connected dominating set problems
AU - Khuller, Samir
AU - Purohit, Manish
AU - Sarpatwar, Kanthi K.
N1 - Publisher Copyright:
© 2020 Society for Industrial and Applied Mathematics.
PY - 2020
Y1 - 2020
N2 - We study partial and budgeted versions of the well-studied connected dominating set problem. In the partial connected dominating set (PCDS) problem, we are given an undirected graph G = (V;E) and an integer n0, and the goal is to find a minimum subset of vertices that induces a connected subgraph of G and dominates at least n0 vertices. We obtain the first polynomial time algorithm with an O(ln Δ) approximation guarantee for this problem, thereby significantly extending the results of Guha and Khuller [Algorithmica, 20(1998), pp. 374-387] for the connected dominating set problem. We note that none of the methods developed earlier can be applied directly to solve this problem. In the budgeted connected dominating set problem, there is a budget on the number of vertices we can select, and the goal is to dominate as many vertices as possible. We obtain a 1 12 (1-1 e) approximation algorithm for this problem. Finally, we show that our techniques extend to a more general setting where the profit function associated with a subset of vertices is a "special" submodular function. This generalization captures the connected dominating set problem with capacities and/or weighted profits as special cases. This implies an O(ln q) approximation (where q denotes the quota) and O(1) approximation algorithms for the partial and budgeted versions of these problems. While the algorithms are simple, the results make a surprising use of the greedy set cover framework in defining a useful profit function. Finally, we prove that (both edge and node) weighted versions of the PCDS problem are as hard as the more general group Steiner tree problem.
AB - We study partial and budgeted versions of the well-studied connected dominating set problem. In the partial connected dominating set (PCDS) problem, we are given an undirected graph G = (V;E) and an integer n0, and the goal is to find a minimum subset of vertices that induces a connected subgraph of G and dominates at least n0 vertices. We obtain the first polynomial time algorithm with an O(ln Δ) approximation guarantee for this problem, thereby significantly extending the results of Guha and Khuller [Algorithmica, 20(1998), pp. 374-387] for the connected dominating set problem. We note that none of the methods developed earlier can be applied directly to solve this problem. In the budgeted connected dominating set problem, there is a budget on the number of vertices we can select, and the goal is to dominate as many vertices as possible. We obtain a 1 12 (1-1 e) approximation algorithm for this problem. Finally, we show that our techniques extend to a more general setting where the profit function associated with a subset of vertices is a "special" submodular function. This generalization captures the connected dominating set problem with capacities and/or weighted profits as special cases. This implies an O(ln q) approximation (where q denotes the quota) and O(1) approximation algorithms for the partial and budgeted versions of these problems. While the algorithms are simple, the results make a surprising use of the greedy set cover framework in defining a useful profit function. Finally, we prove that (both edge and node) weighted versions of the PCDS problem are as hard as the more general group Steiner tree problem.
KW - Approximation algorithms
KW - Connected dominating set
KW - Partial and budgeted connected dominating set
KW - Sub-modular optimization
UR - http://www.scopus.com/inward/record.url?scp=85079753572&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85079753572&partnerID=8YFLogxK
U2 - 10.1137/18M1212094
DO - 10.1137/18M1212094
M3 - Article
AN - SCOPUS:85079753572
VL - 34
SP - 251
EP - 270
JO - SIAM Journal on Discrete Mathematics
JF - SIAM Journal on Discrete Mathematics
SN - 0895-4801
IS - 1
ER -