Finding Diameter-Reducing Shortcuts in Trees

Abstract

In the \emph{$k$-Diameter-Optimally Augmenting Tree Problem} we are given a tree $T$ of $n$ vertices as input. The tree is embedded in an unknown \emph{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\ge 3$. For any constant $\epsilon >0$, we instead design a linear-time $(1+\epsilon )$-approximation algorithm for paths and $k=o(\sqrt{\log n})$, thus establishing a dichotomy between paths and trees for $k\ge 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(nk\log n)$ even for non-metric graphs. Our data structure and the latter result are of independent interest.

22 pages, 6 figures, WADS 2023