TY - GEN

T1 - Ruling sets in random order and adversarial streams

AU - Assadi, Sepehr

AU - Dudeja, Aditi

N1 - Publisher Copyright:
© Sepehr Assadi and Aditi Dudeja; licensed under Creative Commons License CC-BY 4.0

PY - 2021/10/1

Y1 - 2021/10/1

N2 - 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.

AB - 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.

KW - Communication Complexity

KW - Lower bounds

KW - Ruling sets

KW - Symmetry breaking

UR - http://www.scopus.com/inward/record.url?scp=85118162282&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85118162282&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.DISC.2021.6

DO - 10.4230/LIPIcs.DISC.2021.6

M3 - Conference contribution

AN - SCOPUS:85118162282

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 35th International Symposium on Distributed Computing, DISC 2021

A2 - Gilbert, Seth

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 35th International Symposium on Distributed Computing, DISC 2021

Y2 - 4 October 2021 through 8 October 2021

ER -