Improving the dilation of a metric graph by adding edges

Abstract

Most of the literature on spanners focuses on building the graph from scratch. This paper instead focuses on adding edges to improve an existing graph. A major open problem in this field is: given a graph embedded in a metric space, and a budget of $k$ edges, which $k$ edges do we add to produce a minimum-dilation graph? The special case where $k=1$ has been studied in the past, but no major breakthroughs have been made for $k>1$. We provide the first positive result, an $O(k)$-approximation algorithm that runs in $O(n^3\log n)$ time.

arXiv commentJournal version, TALG 2022