# Item

ITEM ACTIONSEXPORT

Released

Paper

#### Distributed Distance-r Dominating Set on Sparse High-Girth Graphs

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

arXiv:1910.02794.pdf

(Preprint), 528KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Amiri, S. A., & Wiederhake, B. (2020). Distributed Distance-r Dominating Set on Sparse High-Girth Graphs. Retrieved from https://arxiv.org/abs/1910.02794.

Cite as: https://hdl.handle.net/21.11116/0000-0007-905B-0

##### Abstract

The dominating set problem and its generalization, the distance-$r$

dominating set problem, are among the well-studied problems in the sequential

settings. In distributed models of computation, unlike for domination, not much

is known about distance-r domination. This is actually the case for other

important closely-related covering problem, namely, the distance-$r$

independent set problem. By result of Kuhn et al. we know the distributed

domination problem is hard on high girth graphs; we study the problem on a

slightly restricted subclass of these graphs: 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 to $r$, not to the size of the graph. This is the first algorithm

that shows there are non-trivial constant factor approximations in constant

number of rounds for any distance $r$-covering problem in distributed settings.

To show the dependency on r is inevitable, we provide an unconditional lower

bound showing 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.

dominating set problem, are among the well-studied problems in the sequential

settings. In distributed models of computation, unlike for domination, not much

is known about distance-r domination. This is actually the case for other

important closely-related covering problem, namely, the distance-$r$

independent set problem. By result of Kuhn et al. we know the distributed

domination problem is hard on high girth graphs; we study the problem on a

slightly restricted subclass of these graphs: 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 to $r$, not to the size of the graph. This is the first algorithm

that shows there are non-trivial constant factor approximations in constant

number of rounds for any distance $r$-covering problem in distributed settings.

To show the dependency on r is inevitable, we provide an unconditional lower

bound showing 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.