2023/10/11 by Chen, Yu, Tan, Zihan
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2310.07862
In the Steiner point removal (SPR) problem, we are given a (weighted) graph G and a subset T of its vertices called terminals, and the goal is to compute a (weighted) graph H on T that is a minor of G, such that the distance between every pair of terminals is preserved to within some small multiplicative factor, that is called the stretch of H. It has been shown that on general graphs we can achieve stretch O(log |T|) [Filtser, 2018]. On the other hand, the best-known stretch lower bound is 8 [Chan-Xia-Konjevod-Richa, 2006], which holds even for trees. In this work, we show an improved lower bound of Ω(√(log |T|)).