Analyzing the optimal neighborhood: algorithms for budgeted and partial connected dominating set problems

DOI10.1137/1.9781611973402.123MaRDI QIDQ5384085zbMATH OpenOpenAlexFDO

Authors Samir Khuller, Manish Purohit, Kanthi K. Sarpatwar

Publication date 20 June 2019

Published in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1311.2309

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Analysis of algorithms (68W40)

Abstract: We study partial and budgeted versions of the well studied connected dominating set problem. In the partial connected dominating set problem, we are given an undirected graph G = (V,E) and an integer n', and the goal is to find a minimum subset of vertices that induces a connected subgraph of G and dominates at least n' vertices. We obtain the first polynomial time algorithm with an O(ln Delta) approximation factor for this problem, thereby significantly extending the results of Guha and Khuller (Algorithmica, Vol. 20(4), Pages 374-387, 1998) 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/13)(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 monotone "special" submodular function. This generalization captures the connected dominating set problem with capacities and/or weighted profits as special cases. This implies a O(ln q) approximation (where q denotes the quota) and an 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.

Recommendations

• Analyzing the optimal neighborhood: algorithms for partial and budgeted connected dominating set problems
• Improved budgeted connected domination and budgeted edge-vertex domination
• A greedy approximation for minimum connected dominating sets
• Approximation algorithms for connected dominating sets
• A unified greedy approximation for several dominating set problems

Cited in

(19)

• A simple approximation algorithm for minimum weight partial connected set cover
• Selective harvesting over networks
• Maximum rooted connected expansion
• Improved budgeted connected domination and budgeted edge-vertex domination
• Algorithm and complexity of the two disjoint connected dominating sets problem on trees
• On maximum leaf trees and connections to connected maximum cut problems
• Revisiting connected dominating sets: an almost optimal local information algorithm
• An approximation algorithm for maximum weight budgeted connected set cover
• Parameterized dynamic variants of red-blue dominating set
• Maximum rooted connected expansion
• Improved Budgeted Connected Domination and Budgeted Edge-Vertex Domination
• Analyzing the optimal neighborhood: algorithms for partial and budgeted connected dominating set problems
• scientific article; zbMATH DE number 7650099 (Why is no real title available?)
• Approximation algorithms for minimum weight partial connected set cover problem
• scientific article; zbMATH DE number 7724205 (Why is no real title available?)
• Approximation algorithms for the maximum connected submodular functions
• On the connected minimum sum of radii problem
• Residue domination in bounded-treewidth graphs
• Domination and coverage problems under vulnerability constraints

This page was built for publication: Analyzing the optimal neighborhood: algorithms for budgeted and partial connected dominating set problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5384085)