License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2021.6
URN: urn:nbn:de:0030-drops-148086
Go to the corresponding LIPIcs Volume Portal

Assadi, Sepehr ; Dudeja, Aditi

Ruling Sets in Random Order and Adversarial Streams

LIPIcs-DISC-2021-6.pdf (1 MB)


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 random-order streams, where the edges arrive in a random order, we give a semi-streaming 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 non-trivial streaming algorithm for (α,α-1)-ruling sets for all even α > 2.

BibTeX - Entry

  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:1--6:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-148086},
  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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI