TY - JOUR

T1 - The impact of locality in the broadcast congested clique model

AU - Becker, F.

AU - Montealegre, P.

AU - Rapaport, I.

AU - Todinca, I.

N1 - Funding Information:
The second author received partial support from Fondecyt 11190482 and from CONICYT + PAI + Convocatoria Nacional Subvenci?n a Instalaci?n en la Academia Convocatoria A?o 2017 + PAI77170068. The third author acknowledges partial support from CONICYT via Basal in Applied Mathematics and from Fondecyt 1170021.
Funding Information:
\ast Received by the editors December 17, 2018; accepted for publication (in revised form) December 12, 2019; published electronically March 12, 2020. Some results of this work were presented as a brief announcement in the 2016 ACM Symposium on Principles of Distributed Computing. Some other results were presented in the 2018 Latin American Symposium on Theoretical Informatics. https://doi.org/10.1137/18M1233534 Funding: The second author received partial support from Fondecyt 11190482 and from CONICYT + PAI + Convocatoria Nacional Subvenci\o'n a Instalacio\'n en la Academia Convoca-toria An\~o 2017 + PAI77170068. The third author acknowledges partial support from CONICYT via Basal in Applied Mathematics and from Fondecyt 1170021. \dagger Universit\e' d'Orl\e'ans, INSA Centre Val de Loire, LIFO EA 4022, Orl\e'ans, France (florent. becker@univ-orleans.fr, ioan.todinca@univ-orleans.fr). \ddagger Facultad de Ingenier\{\'i}a y Ciencias, Universidad Adolfo Ib\a'n\~ez, Santiago, Chile (p.montealegre@ uai.cl). \S DIM-CMM (UMI 2807 CNRS), Universidad de Chile, Santiago, Chile (rapaport@dim.uchile.cl).
Publisher Copyright:
© 2020 Society for Industrial and Applied Mathematics Publications. All rights reserved.

PY - 2020

Y1 - 2020

N2 - The broadcast congested clique model (BCLIQUE) is a message-passing model of distributed computation where ra nodes communicate with each other in synchronous rounds. First, in this paper we prove that there is a one-round, deterministic algorithm that reconstructs the input graph G if the graph is d-degenerate, and rejects otherwise, using bandwidth b = 0(d - logra). Then, we introduce a new parameter to the model. We study the situation where the nodes, initially, instead of knowing their immediate neighbors, know their neighborhood up to a fixed radius r. In this new framework, denoted BCLIQUE[r], we study the problem of detecting, in G, an induced cycle of length at most k (CYCLEk). We give upper and lower bounds. We show that if each node is allowed to see up to distance r = [k/2\ + 1, then a polylogarithmic bandwidth is sufficient for solving CYCLE>k with only two rounds. Nevertheless, if nodes were allowed to see up to distance r = [k/3], then any one-round algorithm that solves CYCLE>k needs the bandwidth b to be at least Q(ra/ logra). We also show the existence of a one-round, deterministic BCLIQUE algorithm that solves CYCLE

AB - The broadcast congested clique model (BCLIQUE) is a message-passing model of distributed computation where ra nodes communicate with each other in synchronous rounds. First, in this paper we prove that there is a one-round, deterministic algorithm that reconstructs the input graph G if the graph is d-degenerate, and rejects otherwise, using bandwidth b = 0(d - logra). Then, we introduce a new parameter to the model. We study the situation where the nodes, initially, instead of knowing their immediate neighbors, know their neighborhood up to a fixed radius r. In this new framework, denoted BCLIQUE[r], we study the problem of detecting, in G, an induced cycle of length at most k (CYCLEk). We give upper and lower bounds. We show that if each node is allowed to see up to distance r = [k/2\ + 1, then a polylogarithmic bandwidth is sufficient for solving CYCLE>k with only two rounds. Nevertheless, if nodes were allowed to see up to distance r = [k/3], then any one-round algorithm that solves CYCLE>k needs the bandwidth b to be at least Q(ra/ logra). We also show the existence of a one-round, deterministic BCLIQUE algorithm that solves CYCLE

KW - Broadcast congested clique

KW - Graph degeneracy

KW - Induced cycles

UR - http://www.scopus.com/inward/record.url?scp=85090731436&partnerID=8YFLogxK

U2 - 10.1137/18M1233534

DO - 10.1137/18M1233534

M3 - Article

AN - SCOPUS:85090731436

SN - 0895-4801

VL - 34

SP - 682

EP - 700

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 1

ER -