An $\tilde{\Omega }\left(\sqrt{\log |T|}\right)$ Lower Bound for Steiner Point Removal

Yu Chen, Zihan Tan

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$…