Steiner Point Removal with distortion $O(\log k)$, using the Noisy-Voronoi algorithm

Abstract

In the Steiner Point Removal (SPR) problem, we are given a weighted graph $G=(V,E)$ and a set of terminals $K\subset V$ of size $k$. The objective is to find a minor $M$ of $G$ with only the terminals as its vertex set, such that distances between the terminals will be preserved up to a small multiplicative distortion. Kamma, Krauthgamer and Nguyen [SICOMP2015] devised a ball-growing algorithm with exponential distributions to show that the distortion is at most $O({\log }^{5}k)$. Cheung [SODA2018] improved the analysis of the same algorithm, bounding the distortion by $O({\log }^{2}k)$. We devise a novel and simpler algorithm (called the Noisy Voronoi algorithm) which incurs distortion $O(\log k)$. This algorithm can be implemented in almost linear time ($O(|E|\log |V|)$).

A preliminary version was published at SODA'18. The name was slightly modified to emphasize the fact that we analyze a different algorithm in this version