Tight Distance Query Reconstruction for Trees and Graphs Without Long Induced Cycles

ABSTRACT Given access to the vertex set of a connected graph and an oracle that given two vertices , returns the shortest path distance between and , how many queries are needed to reconstruct ? Firstly, we show that randomized algorithms need to use at least queries in expectation to reconstruct ‐vertex trees of maximum degree . The best previous lower bound (for graphs of bounded maximum degree) was an information‐theoretic lower bound of . Our randomized 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 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 using 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 randomized algorithm for chordal graphs used queries in expectation, so we improve by a ‐factor for this graph class.