Breaking the O(ln n) barrier: An enhanced approximation algorithm for fault-tolerant minimum weight connected dominating set

Finding a connected dominating set (CDS) in a given graph is a fundamental problem and has been studied intensively for a long time because of its application in computer science and operations research, e.g., connected facility location and wireless networks. In some cases, fault-tolerance is desirable. Taking wireless networks as an example, since wireless nodes may fail due to accidental damage or energy depletion, it is desirable that the virtual backbone has some fault-tolerance. Such a problem can be modeled as finding a minimum k-connected m-fold dominating set ((k;m)-CDS) of a graph G =(V; E), which is a node set D such that every node outside of D has at least m neighbors in D and the subgraph of G induced by D is k-connected. In this paper, we study the minimum weight (1;m)-CDS problem ((1;m)-MWCDS), and present an (H(σ+m)+2H(σ-1))- approximation algorithm, where σ is the maximum degree of the graph and H is the Harmonic number. Notice that the state-of-the-art algorithm achieves O(ln(n))-approximation factor for the (1; 1)-MWCDS problem, where n is the number of nodes. Our work improves this ratio to O(ln σ) for an even more general problem: (1;m)-MWCDS. Such an improvement also enables us to obtain a (3:67 + α)-approximation for the (1;m)-MWCDS problem on unit disk graph, where α is the performance ratio for the minimum weight m-fold dominating set problem on unit disk graph.