DROPS

Document

Track C: Foundations of Networks and Multi-Agent Systems: Models, Algorithms and Information Management

DOI: 10.4230/LIPIcs.ICALP.2019.132

Distributed Detection of Cliques in Dynamic Networks

Authors: Matthias Bonne and Keren Censor-Hillel

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract

This paper provides an in-depth study of the fundamental problems of finding small subgraphs in distributed dynamic networks. While some problems are trivially easy to handle, such as detecting a triangle that emerges after an edge insertion, we show that, perhaps somewhat surprisingly, other problems exhibit a wide range of complexities in terms of the trade-offs between their round and bandwidth complexities. In the case of triangles, which are only affected by the topology of the immediate neighborhood, some end results are: - The bandwidth complexity of 1-round dynamic triangle detection or listing is Theta(1). - The bandwidth complexity of 1-round dynamic triangle membership listing is Theta(1) for node/edge deletions, Theta(n^{1/2}) for edge insertions, and Theta(n) for node insertions. - The bandwidth complexity of 1-round dynamic triangle membership detection is Theta(1) for node/edge deletions, O(log n) for edge insertions, and Theta(n) for node insertions. Most of our upper and lower bounds are tight. Additionally, we provide almost always tight upper and lower bounds for larger cliques.

Cite as

Matthias Bonne and Keren Censor-Hillel. Distributed Detection of Cliques in Dynamic Networks. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 132:1-132:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bonne_et_al:LIPIcs.ICALP.2019.132,
  author =	{Bonne, Matthias and Censor-Hillel, Keren},
  title =	{{Distributed Detection of Cliques in Dynamic Networks}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{132:1--132:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.132},
  URN =		{urn:nbn:de:0030-drops-107082},
  doi =		{10.4230/LIPIcs.ICALP.2019.132},
  annote =	{Keywords: distributed computing, subgraph detection, dynamic graphs}
}

Search Results

Documents authored by Bonne, Matthias

Distributed Detection of Cliques in Dynamic Networks

Abstract

Cite as

Thanks for your feedback!

Could not send message