License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2023.11
URN: urn:nbn:de:0030-drops-191378
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/19137/
Go to the corresponding LIPIcs Volume Portal

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

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

pdf-format:
LIPIcs-DISC-2023-11.pdf (0.7 MB)

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.

BibTeX - Entry

@InProceedings{cambus_et_al:LIPIcs.DISC.2023.11,
  author =	{Cambus, M\'{e}lanie and Kuhn, Fabian and Pai, Shreyas and Uitto, Jara},
  title =	{{Time and Space Optimal Massively Parallel Algorithm for the 2-Ruling Set Problem}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{11:1--11:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/19137},
  URN =		{urn:nbn:de:0030-drops-191378},
  doi =		{10.4230/LIPIcs.DISC.2023.11},
  annote =	{Keywords: Ruling Sets, Parallel Algorithms, Congested Clique, Massively Parallel Computing, Semi-Streaming}
}

Keywords: Ruling Sets, Parallel Algorithms, Congested Clique, Massively Parallel Computing, Semi-Streaming
Collection: 37th International Symposium on Distributed Computing (DISC 2023)
Issue Date: 2023
Date of publication: 05.10.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI