2026-07-21T23:22:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14808 2024-03-06T10:54:54Z ddc:004 open_access

Ruling Sets in Random Order and Adversarial Streams Assadi, Sepehr Dudeja, Aditi Symmetry breaking Ruling sets Lower bounds Communication Complexity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sepehr Assadi and Aditi Dudeja 2021 Is Part Of LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2021.6 urn:nbn:de:0030-drops-148086 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.6 eng https://creativecommons.org/licenses/by/4.0/legalcode