Time and Space Optimal Massively Parallel Algorithm for the 2-Ruling Set Problem

Mélanie Cambus*, Fabian Kuhn*, Shreyas Pai*, Jara Uitto*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingsScientificpeer-review

24 Downloads (Pure)

Abstract

In this work, we present a constant-round algorithm for the 2-ruling set problem in the Congested Clique model. As a direct consequence, we obtain a constant round algorithm in the MPC model with linear space-per-machine and optimal total space. Our results improve on the O(log log log n)-round algorithm by [HPS, DISC'14] and the O(log log ∆)-round algorithm by [GGKMR, PODC'18]. Our techniques can also be applied to the semi-streaming model to obtain an O(1)-pass algorithm. Our main technical contribution is a novel sampling procedure that returns a small subgraph such that almost all nodes in the input graph are adjacent to the sampled subgraph. An MIS on the sampled subgraph provides a 2-ruling set for a large fraction of the input graph. As a technical challenge, we must handle the remaining part of the graph, which might still be relatively large. We overcome this challenge by showing useful structural properties of the remaining graph and show that running our process twice yields a 2-ruling set of the original input graph with high probability.

Original languageEnglish
Title of host publication37th International Symposium on Distributed Computing, DISC 2023
EditorsRotem Oshman
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
ISBN (Electronic)978-3-95977-301-0
DOIs
Publication statusPublished - Oct 2023
MoE publication typeA4 Conference publication
EventInternational Symposium on Distributed Computing - L'Aquila, Italy
Duration: 10 Oct 202312 Oct 2023
Conference number: 37

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume281
ISSN (Print)1868-8969

Conference

ConferenceInternational Symposium on Distributed Computing
Abbreviated titleDISC
Country/TerritoryItaly
CityL'Aquila
Period10/10/202312/10/2023

Keywords

  • Congested Clique
  • Massively Parallel Computing
  • Parallel Algorithms
  • Ruling Sets
  • Semi-Streaming

Fingerprint

Dive into the research topics of 'Time and Space Optimal Massively Parallel Algorithm for the 2-Ruling Set Problem'. Together they form a unique fingerprint.

Cite this