2 Search Results for "Bonne, Matthias"

Document
DOI: 10.4230/LIPIcs.DISC.2025.22
The Complexity Landscape of Dynamic Distributed Subgraph Finding

Authors: Yi-Jun Chang, Lyuting Chen, Yanyu Chen, Gopinath Mishra, and Mingyang Yang

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
Bonne and Censor-Hillel (ICALP 2019) initiated the study of distributed subgraph finding in dynamic networks of limited bandwidth. For the case where the target subgraph is a clique, they determined the tight bandwidth complexity bounds in nearly all settings. However, several open questions remain, and very little is known about finding subgraphs beyond cliques. In this work, we consider these questions and explore subgraphs beyond cliques in the deterministic setting. For finding cliques, we establish an Ω(log log n) bandwidth lower bound for one-round membership-detection under edge insertions only and an Ω(log log log n) bandwidth lower bound for one-round detection under both edge insertions and node insertions. Moreover, we demonstrate new algorithms to show that our lower bounds are tight in bounded-degree networks when the target subgraph is a triangle. Prior to our work, no lower bounds were known for these problems. For finding subgraphs beyond cliques, we present a complete characterization of the bandwidth complexity of the membership-listing problem for every target subgraph, every number of rounds, and every type of topological change: node insertions, node deletions, edge insertions, and edge deletions. We also show partial characterizations for one-round membership-detection and listing.
Cite as

Yi-Jun Chang, Lyuting Chen, Yanyu Chen, Gopinath Mishra, and Mingyang Yang. The Complexity Landscape of Dynamic Distributed Subgraph Finding. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 22:1-22:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chang_et_al:LIPIcs.DISC.2025.22,
  author =	{Chang, Yi-Jun and Chen, Lyuting and Chen, Yanyu and Mishra, Gopinath and Yang, Mingyang},
  title =	{{The Complexity Landscape of Dynamic Distributed Subgraph Finding}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{22:1--22:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.22},
  URN =		{urn:nbn:de:0030-drops-248399},
  doi =		{10.4230/LIPIcs.DISC.2025.22},
  annote =	{Keywords: Distributed algorithms, dynamic algorithms, subgraph finding}
}
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}
}
  • Refine by Type
  • 2 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2019

  • Refine by Author
  • 1 Bonne, Matthias
  • 1 Censor-Hillel, Keren
  • 1 Chang, Yi-Jun
  • 1 Chen, Lyuting
  • 1 Chen, Yanyu
  • Show More...

  • Refine by Series/Journal
  • 2 LIPIcs

  • Refine by Classification
  • 2 Theory of computation → Distributed algorithms
  • 1 Theory of computation → Distributed computing models

  • Refine by Keyword
  • 1 Distributed algorithms
  • 1 distributed computing
  • 1 dynamic algorithms
  • 1 dynamic graphs
  • 1 subgraph detection
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact