Distributed Symmetry Breaking on Power Graphs via Sparsification

DOI10.1145/3583668.3594579OpenAlexW4380880097WikidataQ130808097 ScholiaQ130808097MaRDI QIDQ6202239FDOQ6202239

Authors Yannic Maus, Jara Uitto 

Publication date 26 March 2024

Published in Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2302.06878

zbMATH Keywords

shatteringdistributed algorithmmaximal independent setsparsificationpower graphsruling setsCONGEST model

Mathematics Subject Classification ID

Distributed algorithms (68W15) Distributed systems (68M14)

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 $G^k$, where each node of the communication network $G$ is connected to all of its $k$-hop neighbors. Our main contribution is a deterministic polylogarithmic time algorithm for computing $k$-ruling sets of $G^k$, which (for $k>1$) improves exponentially on the current state-of-the-art runtimes. The main technical ingredient for this result is a deterministic sparsification procedure which may be of independent interest. On top of being a natural family of problems, ruling sets (in power graphs) are well-motivated 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 $G^k$ in essentially the same time as they can be computed in $G$. We also revisit the shattering algorithm for MIS [BEPS JACM'16] and present different approaches for the post-shattering 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].

Cites work

• scientific article; zbMATH DE number 7650885 (Why is no real title available?)
• scientific article; zbMATH DE number 7758308 (Why is no real title available?)
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A deterministic algorithm for the MST problem in constant rounds of congested clique
• A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs
• An Automatic Speedup Theorem for Distributed Problems
• An Improved Distributed Algorithm for Maximal Independent Set
• Chernoff–Hoeffding Bounds for Applications with Limited Independence
• Correlation clustering in data streams
• Derandomizing local distributed algorithms under bandwidth restrictions
• Deterministic distributed dominating set approximation in the CONGEST model
• Deterministic distributed ruling sets of line graphs
• Distance-2 Coloring in the CONGEST Model
• Distributed Approximation on Power Graphs
• Distributed Computing: A Locality-Sensitive Approach
• Distributed Lower Bounds for Ruling Sets
• Distributed MIS via all-to-all communication
• Distributed Maximal Independent Set using Small Messages
• Distributed Testing of Distance-k Colorings
• Distributed \((\Delta+1)\)-coloring via ultrafast graph shattering
• Distributed algorithms for the Lovász local lemma and graph coloring
• Efficient Deterministic Distributed Coloring with Small Bandwidth
• Improved distributed \(\Delta\)-coloring
• Improved massively parallel computation algorithms for MIS, matching, and vertex cover
• Locality in Distributed Graph Algorithms
• MST in \(O(1)\) rounds of congested clique
• Models and approximation algorithms for channel assignment in radio networks
• Near-additive spanners in low polynomial deterministic CONGEST time
• On the complexity of local distributed graph problems
• Polylogarithmic-time deterministic network decomposition and distributed derandomization
• Sparsifying distributed algorithms with ramifications in massively parallel computation and centralized local computation
• Sublinear algorithms for \((\Delta + 1)\) vertex coloring
• Sublogarithmic distributed algorithms for Lovász local lemma, and the complexity hierarchy
• Super-fast 3-ruling sets
• Superfast coloring in CONGEST via efficient color sampling
• Symmetry breaking depending on the chromatic number or the neighborhood growth
• The Complexity of (Δ+1) Coloring in Congested Clique, Massively Parallel Computation, and Centralized Local Computation
• The locality of distributed symmetry breaking
• Toward more localized local algorithms: removing assumptions concerning global knowledge
• Toward optimal bounds in the congested clique, graph connectivity and MST

This page was built for publication: Distributed Symmetry Breaking on Power Graphs via Sparsification

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6202239)