Deterministic Near-Optimal Distributed Listing of Cliques

DOI10.1145/3519270.3538434MaRDI QIDQ6202171zbMATH OpenOpenAlexWikidataFDO

Authors Keren Censor-Hillel, Dean Leitersdorf

Publication date 26 March 2024

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

Full work available at URL https://arxiv.org/abs/2205.09245

zbMATH Keywords

cliques congest distributed graph algorithms

Mathematics Subject Classification ID

Distributed systems (68M14) Distributed algorithms (68W15)

Abstract: The importance of classifying connections in large graphs has been the motivation for a rich line of work on distributed subgraph finding that has led to exciting recent breakthroughs. A crucial aspect that remained open was whether deterministic algorithms can be as efficient as their randomized counterparts, where the latter are known to be tight up to polylogarithmic factors. We give deterministic distributed algorithms for listing cliques of size

p

in

n^{1 - 2 / p + o (1)}

rounds in the congest model. For triangles, our

n^{1 / 3 + o (1)}

round complexity improves upon the previous state of the art of

n^{2 / 3 + o (1)}

rounds [Chang and Saranurak, FOCS 2020]. For cliques of size

p g e q 4

, ours are the first non-trivial deterministic distributed algorithms. Given known lower bounds, for all values

p g e q 3

our algorithms are tight up to a

n^{o (1)}

subpolynomial factor, which comes from the deterministic routing procedure we use.

Cited in

(2)

This page was built for publication: Deterministic Near-Optimal Distributed Listing of Cliques

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6202171)