# Optimal distance query reconstruction for graphs without long induced cycles

arXiv: https://arxiv.org/abs/2306.05979 · HTML: https://mlsanity.com/paper/2306.05979/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Jun 2023.

## Built on by (most cited first, 3 of 3)

- [Graph Inference with Effective Resistance Queries](https://mlsanity.com/paper/2502.18350/) (2025)
- [Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs](https://mlsanity.com/paper/2506.08405/) (2025)
- [Distance-based Learning of Hypertrees](https://mlsanity.com/paper/2511.22014/) (2025)

## Abstract (arXiv)

Given access to the vertex set V of a connected graph G=(V,E) and an oracle that given two vertices u,v∈ V, returns the shortest path distance between u and v, how many queries are needed to reconstruct E? Firstly, we show that randomised algorithms need to use at least frac1200 Delta nlog_Delta n queries in expectation in order to reconstruct n-vertex trees of maximum degree Delta. The best previous lower bound (for graphs of bounded maximum degree) was an information-theoretic lower bound of Omega(nlog n/log log n). Our randomised lower bound is also the first to break through the information-theoretic barrier for related query models including distance queries for phylogenetic trees, membership queries for learning partitions and path queries in directed trees. Secondly, we provide a simple deterministic algorithm to reconstruct trees using Delta nlog_Delta n+(Delta+2)n distance queries. This proves that our lower bound is optimal up to a multiplicative constant. We extend our algorithm to reconstruct graphs without induced cycles of length at least k using ODelta,k(nlog n) queries. Our lower bound is therefore tight for a wide range of tree-like graphs, such as chordal graphs, permutation graphs and AT-free graphs. The previously best randomised algorithm for chordal graphs used ODelta(nlog2 n) queries in expectation, so we improve by a (log n)-factor for this graph class.