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

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

*Tämän työn vastaava kirjoittaja

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference article in proceedingsScientificvertaisarvioitu

10 Lataukset (Pure)

Abstrakti

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.

AlkuperäiskieliEnglanti
Otsikko37th International Symposium on Distributed Computing, DISC 2023
ToimittajatRotem Oshman
KustantajaSchloss Dagstuhl - Leibniz-Zentrum für Informatik
ISBN (elektroninen)978-3-95977-301-0
DOI - pysyväislinkit
TilaJulkaistu - lokak. 2023
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisussa
TapahtumaInternational Symposium on Distributed Computing - L'Aquila, Italia
Kesto: 10 lokak. 202312 lokak. 2023
Konferenssinumero: 37

Julkaisusarja

NimiLeibniz International Proceedings in Informatics, LIPIcs
Vuosikerta281
ISSN (painettu)1868-8969

Conference

ConferenceInternational Symposium on Distributed Computing
LyhennettäDISC
Maa/AlueItalia
KaupunkiL'Aquila
Ajanjakso10/10/202312/10/2023

Sormenjälki

Sukella tutkimusaiheisiin 'Time and Space Optimal Massively Parallel Algorithm for the 2-Ruling Set Problem'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä