2018/08/08 by Filtser, Arnold
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1808.02800
In the Steiner Point Removal (SPR) problem, we are given a weighted graph G=(V,E) and a set of terminals K⊂ 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(log5 k). Cheung [SODA2018] improved the analysis of the same algorithm, bounding the distortion by O(log2 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|)).