2023/06/09 by Paul Bastide, Bastide, Paul, Carla Groenland +1 · 3 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced biosensing and bioanalysis techniques #Algorithms and Data Compression #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.2 #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.2306.05979
openalex publication_date 2023/06/09 · openalex created_date 2023/06/13 · openalex updated_date 2026/07/28
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 ΔnlogΔn queries in expectation in order to reconstruct n-vertex trees of maximum degree Δ. The best previous lower bound (for graphs of bounded maximum degree) was an information-theoretic lower bound of Ω(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 ΔnlogΔn+(Δ+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 OΔ,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 OΔ(nlog2 n) queries in expectation, so we improve by a (log n)-factor for this graph class.