Improved Lower Bound for Steiner Point Removal

Abstract

In the Steiner Point Removal problem, we are given a graph $G=(V,E)$ with an edge-length function ${\ell }_G:E\to {\mathbb{R}}_{+}$ and a subset $T\subseteq V$ of terminals. The goal is to find a minor $H=(T,E_H)$ of $G$ on vertex set $T$ such that the shortest path metric derived from $G$ on the edges of $H$ preserves the distance between every pair of terminals within a small multiplicative stretch. Filtser proved that a stretch of $O(\log |T|)$ can be achieved (in polynomial time), while Chen and Tan more recently proved a lower bound of $\Omega \left(\sqrt{\frac{\log |T|}{\log \log |T|}}\right)$ on the achievable stretch. Their lower bound is via a simple construction involving low-degree high-girth graphs. The existence of such graphs is guaranteed through the existence of low-degree high-girth expanders. In this work, we improve the lower bound to $\Omega (\sqrt{\log |T|})$ using the same simple construction of Chen and Tan but with a more careful analysis that exploits the expansion property.