Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2411.11544 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915456155123712 |
|---|---|
| author | Chang, Yi-Jun Chen, Lyuting Chen, Yanyu Mishra, Gopinath Yang, Mingyang |
| author_facet | Chang, Yi-Jun Chen, Lyuting Chen, Yanyu Mishra, Gopinath Yang, Mingyang |
| contents | 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 \emph{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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_11544 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Complexity Landscape of Dynamic Distributed Subgraph Finding Chang, Yi-Jun Chen, Lyuting Chen, Yanyu Mishra, Gopinath Yang, Mingyang Data Structures and Algorithms 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 \emph{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. |
| title | The Complexity Landscape of Dynamic Distributed Subgraph Finding |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2411.11544 |