An O(log² n)-approximation algorithm for 2-edge-connected dominating set

2019/12/20 by Belgi, Amir, Nutov, Zeev
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1912.09662

Abstract

In the Connected Dominating Set problem we are given a graph G=(V,E) and seek a minimum size dominating set S ⊆ V such that the subgraph G[S] of G induced by S is connected. In the 2-Edge-Connected Dominating Set problem G[S] should be 2-edge-connected. We give the first non-trivial approximation algorithm for this problem, with expected approximation ratio O(log²n).

Related

• Improved approximation algorithms for k-connected m-dominating set problems
• Approximation algorithms and hardness for domination with propagation
• 2-node-connectivity network design
• Disjoint Dominating and 2-Dominating Sets in Graphs: Hardness and Approximation results
• On the Approximability and Hardness of the Minimum Connected Dominating Set with Routing Cost Constraint