Finding Diameter-Reducing Shortcuts in Trees
share
In the k-Diameter-Optimally Augmenting Tree Problem we are given a tree T of n vertices as input. The tree is embedded in an unknown metric space and we have unlimited access to an oracle that, given two distinct vertices u and v of T, can answer queries reporting the cost of the edge (u,v) in constant time. We want to augment T with k shortcuts in order to minimize the diameter of the resulting graph. For k=1, O(n log n) time algorithms are known both for paths [Wang, CG 2018] and trees [Bilò, TCS 2022]. In this paper we investigate the case of multiple shortcuts. We show that no algorithm that performs o(n^2) queries can provide a better than 10/9-approximate solution for trees for k≥ 3. For any constant ε > 0, we instead design a linear-time (1+ε)-approximation algorithm for paths and k = o(√(log n)), thus establishing a dichotomy between paths and trees for k≥ 3. We achieve the claimed running time by designing an ad-hoc data structure, which also serves as a key component to provide a linear-time 4-approximation algorithm for trees, and to compute the diameter of graphs with n + k - 1 edges in time O(n k log n) even for non-metric graphs. Our data structure and the latter result are of independent interest.
READ FULL TEXT