Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915354487291904 |
|---|---|
| author | Black, Hadley Mazumdar, Arya Saha, Barna Xu, Yinzhan |
| author_facet | Black, Hadley Mazumdar, Arya Saha, Barna Xu, Yinzhan |
| contents | The graph reconstruction problem has been extensively studied under various query models. In this paper, we propose a new query model regarding the number of connected components, which is one of the most basic and fundamental graph parameters. Formally, we consider the problem of reconstructing an $n$-node $m$-edge graph with oracle queries of the following form: provided with a subset of vertices, the oracle returns the number of connected components in the induced subgraph. We show $Θ(\frac{m \log n}{\log m})$ queries in expectation are both sufficient and necessary to adaptively reconstruct the graph. In contrast, we show that $Ω(n^2)$ non-adaptive queries are required, even when $m = O(n)$. We also provide an $O(m\log n + n\log^2 n)$ query algorithm using only two rounds of adaptivity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_08405 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs Black, Hadley Mazumdar, Arya Saha, Barna Xu, Yinzhan Data Structures and Algorithms Information Theory Machine Learning The graph reconstruction problem has been extensively studied under various query models. In this paper, we propose a new query model regarding the number of connected components, which is one of the most basic and fundamental graph parameters. Formally, we consider the problem of reconstructing an $n$-node $m$-edge graph with oracle queries of the following form: provided with a subset of vertices, the oracle returns the number of connected components in the induced subgraph. We show $Θ(\frac{m \log n}{\log m})$ queries in expectation are both sufficient and necessary to adaptively reconstruct the graph. In contrast, we show that $Ω(n^2)$ non-adaptive queries are required, even when $m = O(n)$. We also provide an $O(m\log n + n\log^2 n)$ query algorithm using only two rounds of adaptivity. |
| title | Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs |
| topic | Data Structures and Algorithms Information Theory Machine Learning |
| url | https://arxiv.org/abs/2506.08405 |