Graph Reconstruction with a Connected Components Oracle
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_ | 1866914033009950720 |
|---|---|
| author | Harviainen, Juha Parviainen, Pekka |
| author_facet | Harviainen, Juha Parviainen, Pekka |
| contents | In the Graph Reconstruction (GR) problem, the goal is to recover a hidden graph by utilizing some oracle that provides limited access to the structure of the graph. The interest is in characterizing how strong different oracles are when the complexity of an algorithm is measured in the number of performed queries. We study a novel oracle that returns the set of connected components (CC) on the subgraph induced by the queried subset of vertices. Our main contributions are as follows:
1. For a hidden graph with $n$ vertices, $m$ edges, maximum degree $Δ$, and treewidth $k$, GR can be solved in $O(\min\{m / \log m, Δ^2, k^2\} \cdot \log n)$ CC queries by an adaptive randomized algorithm.
2. For a hidden graph with $n$ vertices and degeneracy $d$, GR can be solved in $O(d^2 \log^2 n)$ CC queries by an adaptive randomized algorithm.
3. For a hidden graph with $n$ vertices, $m$ edges, maximum degree $Δ$, and treewidth $k$, no algorithm can solve GR in $o(\min\{m, Δ^2, k^2\})$ CC queries. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_05002 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Graph Reconstruction with a Connected Components Oracle Harviainen, Juha Parviainen, Pekka Data Structures and Algorithms In the Graph Reconstruction (GR) problem, the goal is to recover a hidden graph by utilizing some oracle that provides limited access to the structure of the graph. The interest is in characterizing how strong different oracles are when the complexity of an algorithm is measured in the number of performed queries. We study a novel oracle that returns the set of connected components (CC) on the subgraph induced by the queried subset of vertices. Our main contributions are as follows: 1. For a hidden graph with $n$ vertices, $m$ edges, maximum degree $Δ$, and treewidth $k$, GR can be solved in $O(\min\{m / \log m, Δ^2, k^2\} \cdot \log n)$ CC queries by an adaptive randomized algorithm. 2. For a hidden graph with $n$ vertices and degeneracy $d$, GR can be solved in $O(d^2 \log^2 n)$ CC queries by an adaptive randomized algorithm. 3. For a hidden graph with $n$ vertices, $m$ edges, maximum degree $Δ$, and treewidth $k$, no algorithm can solve GR in $o(\min\{m, Δ^2, k^2\})$ CC queries. |
| title | Graph Reconstruction with a Connected Components Oracle |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2509.05002 |