Distributed Symmetry Breaking on Power Graphs via Sparsification

DOI10.1145/3583668.3594579arXiv2302.06878OpenAlexW4380880097WikidataQ130808097 ScholiaQ130808097MaRDI QIDQ6202239FDOQ6202239

Jara Uitto, Yannic Maus, Author name not available (Why is that?)

Publication date: 26 March 2024

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Distributed Computing: A Locality-Sensitive Approach
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• Locality in Distributed Graph Algorithms
• Chernoff–Hoeffding Bounds for Applications with Limited Independence
• Symmetry breaking depending on the chromatic number or the neighborhood growth
• A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs
• Models and approximation algorithms for channel assignment in radio networks
• The Locality of Distributed Symmetry Breaking
• Deterministic Distributed Dominating Set Approximation in the CONGEST Model
• A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths
• Correlation clustering in data streams
• An Improved Distributed Algorithm for Maximal Independent Set
• Polylogarithmic-time deterministic network decomposition and distributed derandomization
• Toward optimal bounds in the congested clique, graph connectivity and MST
• Super-Fast 3-Ruling Sets.
• A deterministic algorithm for the MST problem in constant rounds of congested clique
• Efficient Deterministic Distributed Coloring with Small Bandwidth
• Distributed algorithms for the Lovász local lemma and graph coloring
• Deterministic distributed ruling sets of line graphs
• Improved distributed \(\Delta\)-coloring
• On the complexity of local distributed graph problems
• Sublogarithmic distributed algorithms for Lovász local lemma, and the complexity hierarchy
• Near-Additive Spanners In Low Polynomial Deterministic CONGEST Time
• The Complexity of (Δ+1) Coloring in Congested Clique, Massively Parallel Computation, and Centralized Local Computation
• Sparsifying Distributed Algorithms with Ramifications in Massively Parallel Computation and Centralized Local Computation
• Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover
• Distributed MIS via All-to-All Communication
• An Automatic Speedup Theorem for Distributed Problems
• Distributed Lower Bounds for Ruling Sets
• Sublinear Algorithms for (Δ + 1) Vertex Coloring
• Toward more localized local algorithms: removing assumptions concerning global knowledge
• Derandomizing local distributed algorithms under bandwidth restrictions
• Distributed Maximal Independent Set using Small Messages
• Distributed Testing of Distance-k Colorings
• Distributed $(\Delta+1)$-Coloring via Ultrafast Graph Shattering
• Distance-2 Coloring in the CONGEST Model
• Distributed Approximation on Power Graphs
• Superfast coloring in CONGEST via efficient color sampling

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)