# Improved Lower Bound for Steiner Point Removal

Preprint · Karthekeyan Chandrasekaran, Chandra Chekuri, Qingyun Chen, Weihao Zhu

- Archive id: arxiv:2610.00177
- Published: 2026-09-16
- arXiv: https://arxiv.org/abs/2610.00177
- Source URL: https://arxiv.org/abs/2610.00177
- PDF: https://arxiv.org/pdf/2610.00177
- Provenance: arxiv

## Abstract

In the Steiner Point Removal problem, we are given a graph $G=(V,E)$ with an edge-length function $\\ell\_G: E\\rightarrow \\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 $Ω\\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 $Ω(\\sqrt{\\log \|T\|})$ using the same simple construction of Chen and Tan but with a more careful analysis that exploits the expansion property.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.