Optimal distance query reconstruction for graphs without long induced cycles

arXiv2306.05979MaRDI QIDQ6439804FDOQ6439804

Authors: Paul Bastide, Carla Groenland 

Publication date: 9 June 2023

Abstract: Let $G=(V,E)$ be an $n$-vertex connected graph of maximum degree $Delta$. Given access to $V$ and an oracle that given two vertices $u,vinV$, returns the shortest path distance between $u$ and $v$, how many queries are needed to reconstruct $E$? We give a simple deterministic algorithm to reconstruct trees using $Deltanlo{g}_{D}eltan+(Delta+2)n$ distance queries and show that even randomised algorithms need to use at least $frac1100Deltanlo{g}_{D}eltan$ queries in expectation. The best previous lower bound was an information-theoretic lower bound of $Omega(nlogn/loglogn)$. Our lower bound also extends to related query models including distance queries for phylogenetic trees, membership queries for learning partitions and path queries in directed trees. We extend our deterministic algorithm to reconstruct graphs without induced cycles of length at least $k$ using $O_{Delta,k}(nlogn)$ queries, which includes various graph classes of interest such as chordal graphs, permutation graphs and AT-free graphs. Since the previously best known randomised algorithm for chordal graphs uses $O_{Delta}(nlo{g}^{2}n)$ queries in expectation, we both get rid off the randomness and get the optimal dependency in $n$ for chordal graphs and various other graph classes. Finally, we build on an algorithm of Kannan, Mathieu, and Zhou [ICALP, 2015] to give a randomised algorithm for reconstructing graphs of treelength $k$ using $O_{Delta,k}(nlo{g}^{2}n)$ queries in expectation.

This page was built for publication: Optimal distance query reconstruction for graphs without long induced cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6439804)