Bicriteria approximation for minimum dilation graph augmentation

Abstract

Spanner constructions focus on the initial design of the network. However, networks tend to improve over time. In this paper, we focus on the improvement step. Given a graph and a budget $k$, which $k$ edges do we add to the graph to minimise its dilation? Gudmundsson and Wong [TALG'22] provided the first positive result for this problem, but their approximation factor is linear in $k$. Our main result is a $(2\sqrt[r]{2}{k}^{1/r},2r)$-bicriteria approximation that runs in $O(n^3\log n)$ time, for all $r\ge 1$. In other words, if $t^{\ast }$ is the minimum dilation after adding any $k$ edges to a graph, then our algorithm adds $O(k^{1+1/r})$ edges to the graph to obtain a dilation of $2r{t}^{\ast }$. Moreover, our analysis of the algorithm is tight under the Erdős girth conjecture.

To appear in ESA 2024