2026-07-26T02:55:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22246 2024-12-05T15:32:41Z ddc:004 open_access

Quasi-Linear Distance Query Reconstruction for Graphs of Bounded Treelength Bastide, Paul Groenland, Carla Distance Reconstruction Randomized Algorithm Treelength In distance query reconstruction, we wish to reconstruct the edge set of a hidden graph by asking as few distance queries as possible to an oracle. Given two vertices u and v, the oracle returns the shortest path distance between u and v in the graph. The length of a tree decomposition is the maximum distance between two vertices contained in the same bag. The treelength of a graph is defined as the minimum length of a tree decomposition of this graph. We present an algorithm to reconstruct an n-vertex connected graph G parameterized by maximum degree Δ and treelength k in O_{k,Δ}(n log² n) queries (in expectation). This is the first algorithm to achieve quasi-linear complexity for this class of graphs. The proof goes through a new lemma that could give independent insight on graphs of bounded treelength. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Paul Bastide and Carla Groenland 2024 Is Part Of LIPIcs, Volume 321, 19th International Symposium on Parameterized and Exact Computation (IPEC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2024.20 urn:nbn:de:0030-drops-222465 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2024.20 eng https://creativecommons.org/licenses/by/4.0/legalcode