Near-Optimal Distributed Approximation of Minimum-Weight Connected Dominating Set

This paper(1) presents a near-optimal distributed approximation algorithm for the minimum-weight connected dominating set (MCDS) problem. We use the standard distributed message passing model called the CONGEST model in which in each round each node can send O(log n) bits to each neighbor. The presented algorithm finds an O(log n) approximation in (O) over tilde (D + root n) rounds, where D is the network diameter and n is the number of nodes. MCDS is a classical NP-hard problem and the achieved approximation factor O(log n) is known to be optimal up to a constant factor, unless P = NP. Furthermore, the (O) over tilde (D + root n) round complexity is known to be optimal modulo logarithmic factors (for any approximation), following [Das Sarma et al.-STOC'11].