Ruling sets in random order and adversarial streams

Sepehr Assadi, Aditi Dudeja

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

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 Õ(n4/3) space, improving upon the best known algorithm due to Konrad et al. [DISC 2019], with space Õ(n3/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.

Original languageEnglish (US)
Title of host publication35th International Symposium on Distributed Computing, DISC 2021
EditorsSeth Gilbert
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772105
DOIs
StatePublished - Oct 1 2021
Event35th International Symposium on Distributed Computing, DISC 2021 - Virtual, Freiburg, Germany
Duration: Oct 4 2021Oct 8 2021

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume209
ISSN (Print)1868-8969

Conference

Conference35th International Symposium on Distributed Computing, DISC 2021
Country/TerritoryGermany
CityVirtual, Freiburg
Period10/4/2110/8/21

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Communication Complexity
  • Lower bounds
  • Ruling sets
  • Symmetry breaking

Fingerprint

Dive into the research topics of 'Ruling sets in random order and adversarial streams'. Together they form a unique fingerprint.

Cite this