TY - GEN
T1 - The impact of locality on the detection of cycles in the broadcast congested clique model
AU - Becker, Florent
AU - Montealegre, Pedro
AU - Rapaport, Ivan
AU - Todinca, Ioan
N1 - Publisher Copyright:
© Springer International Publishing AG, part of Springer Nature 2018.
PY - 2018
Y1 - 2018
N2 - The broadcast congested clique model is a message-passing model of distributed computation where n nodes communicate with each other in synchronous rounds. The joint input to the n nodes is an undirected graph G on the same set of nodes, with each node receiving the list of its immediate neighbors in G. In each round each node sends the same message to all other nodes, depending on its own input, on the messages it has received so far, and on a public sequence of random bits. One parameter of this model is an upper bound b on the size of the messages, also known as bandwidth. In this paper we introduce another 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 we study one of the hardest problems in distributed graph algorithms, this is, the problem of detecting, in G, an induced cycle of length at most k (CYCLE≤k) and the problem of detecting in G an induced cycle of length at least k + 1 (CYCLE>k). For r= 1, we exhibit a deterministic, one-round algorithm for solving CYCLE≤k with b= O(n2/klog n) if k is even, and b= O(n2/(k-1)log n) if k is odd. We also prove, assuming the Erdős Girth Conjecture, that this result is tight for k≥ 4, up to logarithmic factors. More precisely, if each node, instead of being able to see only its immediate neighbors, is allowed to see up to distance r= ⌊ k/ 4 ⌋, and if we also allowed randomization and multiple rounds, then the number of rounds R needed to solve CYCLE≤k must be such that R· b= Ω(n2/k) if k is even, and R· b= Ω(n2/(k-1)) if k is odd. On the other hand, 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 Ω(n/ log n).
AB - The broadcast congested clique model is a message-passing model of distributed computation where n nodes communicate with each other in synchronous rounds. The joint input to the n nodes is an undirected graph G on the same set of nodes, with each node receiving the list of its immediate neighbors in G. In each round each node sends the same message to all other nodes, depending on its own input, on the messages it has received so far, and on a public sequence of random bits. One parameter of this model is an upper bound b on the size of the messages, also known as bandwidth. In this paper we introduce another 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 we study one of the hardest problems in distributed graph algorithms, this is, the problem of detecting, in G, an induced cycle of length at most k (CYCLE≤k) and the problem of detecting in G an induced cycle of length at least k + 1 (CYCLE>k). For r= 1, we exhibit a deterministic, one-round algorithm for solving CYCLE≤k with b= O(n2/klog n) if k is even, and b= O(n2/(k-1)log n) if k is odd. We also prove, assuming the Erdős Girth Conjecture, that this result is tight for k≥ 4, up to logarithmic factors. More precisely, if each node, instead of being able to see only its immediate neighbors, is allowed to see up to distance r= ⌊ k/ 4 ⌋, and if we also allowed randomization and multiple rounds, then the number of rounds R needed to solve CYCLE≤k must be such that R· b= Ω(n2/k) if k is even, and R· b= Ω(n2/(k-1)) if k is odd. On the other hand, 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 Ω(n/ log n).
KW - Broadcast congested clique
KW - Graph degeneracy
KW - Induced cycles
UR - http://www.scopus.com/inward/record.url?scp=85045412371&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-77404-6_11
DO - 10.1007/978-3-319-77404-6_11
M3 - Conference contribution
AN - SCOPUS:85045412371
SN - 9783319774039
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 134
EP - 145
BT - LATIN 2018
A2 - Mosteiro, Miguel A.
A2 - Bender, Michael A.
A2 - Farach-Colton, Martin
PB - Springer Verlag
T2 - 13th International Symposium on Latin American Theoretical Informatics, LATIN 2018
Y2 - 16 April 2018 through 19 April 2018
ER -