Graph Reconstruction with a Connected Components Oracle
By: Juha Harviainen, Pekka Parviainen
Potential Business Impact:
Finds hidden connections by asking about groups.
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 $\Delta$, and treewidth $k$, GR can be solved in $O(\min\{m, \Delta^2, k^2\} \cdot \log n)$ CC queries by an adaptive randomized algorithm. 2. For a hidden graph with $n$ vertices, $m$ edges, maximum degree $\Delta$, and treewidth $k$, no algorithm can solve GR in $o(\min\{m, \Delta^2, k^2\})$ CC queries.
Similar Papers
Graph Reconstruction with a Connected Components Oracle
Data Structures and Algorithms
Finds hidden connections by asking about groups.
Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs
Data Structures and Algorithms
Finds hidden connections in networks using a new tool.
On $k$-connectivity oracles in $k$-connected graphs
Data Structures and Algorithms
Finds many paths between two points.