AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

Dominating set and its generalization, the distance-r dominating set problem, are well-studied problems in the sequential settings. In distributed models of computation, not as much is known about distance-r domination. This problem is non-trivial, as naively running a regular dominating set algorithm on G^r would need to deal with very dense graphs, throwing away the underlying structure of G. We study the problem on a restricted subclass: graphs of bounded expansion with high girth, i.e. their girth should be at least 4r+ 3. We show that in such graphs, for every constant r, a simple greedy CONGEST algorithm provides a constant-factor approximation of the minimum distance-r dominating set problem, in a constant number of rounds. More precisely, our constants are dependent on r, but not on the size of the graph. This is the first algorithm that shows that there are non-trivial constant factor approximations in constant number of rounds for distance-r dominating set, and in fact many other distance-r covering problem in distributed settings. To show the dependency on r is inevitable, we provide an unconditional lower bound showing that the same problem is hard already on rings. We also show that our analysis of the algorithm is relatively tight, that is any significant improvement to the approximation factor requires new algorithmic ideas.

This is a trial run for the talk we will give at CIAC 2021 in May.

Sándor Kisfaludi-Bak

+49 681 9325 0

--email hidden

Zoom

527 278 8807

passcode not visible

logged in users only