Revisiting Connected Dominating Sets: An Almost Optimal Local Information Algorithm

In this paper we consider the classical connected dominating set problem. Twenty years ago, Guha and Khuller developed two algorithms for this problem—a centralized greedy approach with an approximation guarantee of H(Δ) + 2 , and a local information greedy approach with an approximation guarantee of 2 (H(Δ) + 1) (where H() is the harmonic function, and Δ is the maximum degree in the graph). A local information greedy algorithm uses significantly less knowledge about the graph, and can be useful in a variety of contexts. However, a fundamental question remained—can we get a local information greedy algorithm with the same performance guarantee as the global greedy algorithm without the penalty of the multiplicative factor of “2” in the approximation factor? In this paper, we answer that question in the affirmative.