Reconstructing Bounded Treelength Graphs with Linearithmic Shortest Path Distance Queries
This provides an efficient solution for graph reconstruction in theoretical computer science, though it is incremental as it refines prior bounds for specific graph classes.
The paper tackles the problem of reconstructing bounded degree and bounded treelength graphs using shortest path distance queries, achieving a deterministic algorithm with O(n log n) queries, which improves the best known by a log n factor and matches a lower bound for a subclass.
We consider the following graph reconstruction problem: given an unweighted connected graph $G = (V,E)$ with visible vertex set $V$ and an oracle which takes two vertices $u,v \in V$ and returns the shortest path distance between $u$ and $v$, how many queries are needed to reconstruct $E$? Specifically, we consider bounded degree $Δ$ and bounded treelength $\mathrm{tl}$ connected graphs and show that reconstruction can be done in $O_{Δ,\mathrm{tl}}(n \log n)$ queries with a deterministic algorithm. This result improves over the best known algorithm (deterministic or randomized) for this graph class by a $\log n$ factor and matches the known lower bound for the class of graphs with bounded chordality, which is a subclass of bounded treelength graphs.