2026-07-26T00:39:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21255 2024-10-24T07:40:08Z ddc:004 open_access

Massively Parallel Ruling Set Made Deterministic Giliberti, Jeff Parsaeian, Zahra deterministic algorithms distributed computing massively parallel computation graph algorithms derandomization We study the deterministic complexity of the 2-Ruling Set problem in the model of Massively Parallel Computation (MPC) with linear and strongly sublinear local memory. - Linear MPC: We present a constant-round deterministic algorithm for the 2-Ruling Set problem that matches the randomized round complexity recently settled by Cambus, Kuhn, Pai, and Uitto [DISC'23], and improves upon the deterministic O(log log n)-round algorithm by Pai and Pemmaraju [PODC'22]. Our main ingredient is a simpler analysis of CKPU’s algorithm based solely on bounded independence, which makes its efficient derandomization possible. - Sublinear MPC: We present a deterministic algorithm that computes a 2-Ruling Set in Õ(√{log n}) rounds deterministically. Notably, this is the first deterministic ruling set algorithm with sublogarithmic round complexity, improving on the O(log Δ + log log^* n)-round complexity that stems from the deterministic MIS algorithm of Czumaj, Davies, and Parter [TALG'21]. Our result is based on a simple and fast randomness-efficient construction that achieves the same sparsification as that of the randomized Õ(√{log n})-round LOCAL algorithm by Kothapalli and Pemmaraju [FSTTCS'12]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jeff Giliberti and Zahra Parsaeian 2024 Is Part Of LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2024.29 urn:nbn:de:0030-drops-212551 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.29 eng https://creativecommons.org/licenses/by/4.0/legalcode