Projects per year
Abstract
In this paper we present efficient distributed algorithms for classical symmetry breaking problems, maximal independent sets (MIS) and ruling sets, in power graphs. We work in the standard CONGEST model of distributed message passing, where the communication network is abstracted as a graph G. Typically, the problem instance in CONGEST is identical to the communication network G, that is, we perform the symmetry breaking in G. In this work, we consider a setting where the problem instance corresponds to a power graph Gk, where each node of the communication network G is connected to all of its khop neighbors.A βruling set is a set of nonadjacent nodes such that each node in G has a ruling neighbor within β hops; a natural generalization of an MIS. On top of being a natural family of problems, ruling sets (in power graphs) are wellmotivated through their applications in the powerful shattering framework [BEPS JACM'16, Ghaffari SODA'19] (and others). We present randomized algorithms for computing maximal independent sets and ruling sets of Gk in essentially the same time as they can be computed in G. Our main contribution is a deterministic poly(k, log n) time algorithm for computing kruling sets of Gk, which (for k > 1) improves exponentially on the current stateoftheart runtimes. Our main technical ingredient for this result is a deterministic sparsification procedure which may be of independent interest.We also revisit the shattering algorithm for MIS [BEPS J'ACM'16] and present different approaches for the postshattering phase. Our solutions are algorithmically and analytically simpler (also in the LOCAL model) than existing solutions and obtain the same runtime as [Ghaffari SODA'16].
Original language  English 

Title of host publication  PODC 2023  Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing 
Publisher  ACM 
Pages  157167 
Number of pages  11 
ISBN (Electronic)  9798400701214 
DOIs  
Publication status  Published  19 Jun 2023 
MoE publication type  A4 Conference publication 
Event  ACM Symposium on Principles of Distributed Computing  Orlando, United States Duration: 19 Jun 2023 → 23 Jun 2023 
Conference
Conference  ACM Symposium on Principles of Distributed Computing 

Abbreviated title  PODC 
Country/Territory  United States 
City  Orlando 
Period  19/06/2023 → 23/06/2023 
Keywords
 CONGEST model
 distributed algorithm
 maximal independent set
 power graphs
 ruling sets
 shattering
 sparsification
Fingerprint
Dive into the research topics of 'Distributed Symmetry Breaking on Power Graphs via Sparsification'. Together they form a unique fingerprint.Projects
 1 Active

: Massively Parallel Algorithms for LargeScale Graph Problems
Uitto, J. (Principal investigator), Cambus, M. (Project Member), Latypov, R. (Project Member) & Pai, S. (Project Member)
01/09/2020 → 27/04/2025
Project: Academy of Finland: Other research funding