Abstract
The goal of this paper is to understand the complexity of a key symmetry breaking problem, namely the (α,β)ruling set problem in the graph streaming model. Given a graph G = (V,E), an (α, β)ruling set is a subset I ⊆ V such that the distance between any two vertices in I is at least α and the distance between a vertex in V and the closest vertex in I is at most β. This is a fundamental problem in distributed computing where it finds applications as a useful subroutine for other problems such as maximal matching, distributed colouring, or shortest paths. Additionally, it is a generalization of MIS, which is a (2,1)ruling set.
Our main results are two algorithms for (2,2)ruling sets:
1) In adversarial streams, where the order in which edges arrive is arbitrary, we give an algorithm with Õ(n^{4/3}) space, improving upon the best known algorithm due to Konrad et al. [DISC 2019], with space Õ(n^{3/2}).
2) In randomorder streams, where the edges arrive in a random order, we give a semistreaming algorithm, that is an algorithm that takes Õ(n) space. Finally, we present new algorithms and lower bounds for (α,β)ruling sets for other values of α and β. Our algorithms improve and generalize the previous work of Konrad et al. [DISC 2019] for (2,β)ruling sets, while our lower bound establishes the impossibility of obtaining any nontrivial streaming algorithm for (α,α1)ruling sets for all even α > 2.
BibTeX  Entry
@InProceedings{assadi_et_al:LIPIcs.DISC.2021.6,
author = {Assadi, Sepehr and Dudeja, Aditi},
title = {{Ruling Sets in Random Order and Adversarial Streams}},
booktitle = {35th International Symposium on Distributed Computing (DISC 2021)},
pages = {6:16:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772105},
ISSN = {18688969},
year = {2021},
volume = {209},
editor = {Gilbert, Seth},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14808},
URN = {urn:nbn:de:0030drops148086},
doi = {10.4230/LIPIcs.DISC.2021.6},
annote = {Keywords: Symmetry breaking, Ruling sets, Lower bounds, Communication Complexity}
}
Keywords: 

Symmetry breaking, Ruling sets, Lower bounds, Communication Complexity 
Collection: 

35th International Symposium on Distributed Computing (DISC 2021) 
Issue Date: 

2021 
Date of publication: 

04.10.2021 