Optimal distance query reconstruction for graphs without long induced cycles

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.