Distributed distance-r covering problems on sparse high-girth graphs

Abstract

We prove that the distance-r dominating set, distance-r connected dominating set, distance-r vertex cover, and distance-r connected vertex cover problems admit constant factor approximations in the CONGEST model of distributed computing in a constant number of rounds on classes of sparse high-girth graphs. In this paper, sparse means bounded expansion, and high-girth means girth at least 4r + 2. Our algorithm is quite simple; however, the proof of its approximation guarantee is non-trivial. To complement the algorithmic results, we show tightness of our approximation by providing a loosely matching lower bound on rings. Our result is the first to show the existence of constant-factor approximations in a constant number of rounds in non-trivial classes of graphs for distance-r covering problems.