Library
local_library Home Repository

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

Journal Article (2025)
Author(s)

P.P. Bastide (TU Delft - Discrete Mathematics and Optimization, CEA)

C.E. Groenland (TU Delft - Discrete Mathematics and Optimization)

Research Group
Discrete Mathematics and Optimization
DOI related publication
https://doi.org/10.1002/rsa.70017
More Info
expand_more
Publication Year
2025
Language
English
Research Group
Discrete Mathematics and Optimization
Issue number
4
Volume number
66
Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Abstract

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