Our main result is that the Steiner Point Removal (SPR) problem can always be solved with polylogarithmic distortion, which answers in the affirmative a question posed by Chan, Xia, Konjevod, and Richa (2006). Specifically, we prove that for every edge-weighted graph @math and a subset of terminals @math , there is a graph @math that is isomorphic to a minor of @math , such that for every two terminals @math , the shortest-path distances between them in @math and in @math satisfy @math . Our existence proof actually gives a randomized polynomial-time algorithm. Our proof features a new variant of metric decomposition. It is well-known that every @math -point metric space @math admits a @math -separating decomposition for @math , which roughly means for every desired diameter bound @math there is a randomized partitioning of @math , which satisfies the following separation requirement: for every @math , the probability they lie in different clusters of the partition is at most @math . We introduce an additional requirement, which is the following tail bound: for every shortest-path @math of length @math , the number of clusters of the partition that meet the path @math , denoted @math , satisfies @math for all @math .
We introduce the following notion of compressing an undirected graph @math with (nonnegative) edge-lengths and terminal vertices @math . A distance-preserving minor is a minor @math (of @math ) with possibly different edge-lengths, such that @math and the shortest-path distance between every pair of terminals is exactly the same in @math and in @math . We ask: what is the smallest @math such that every graph @math with @math terminals admits a distance-preserving minor @math with at most @math vertices? Simple analysis shows that @math . Our main result proves that @math , significantly improving on the trivial @math . Our lower bound holds even for planar graphs @math , in contrast to graphs @math of constant treewidth, for which we prove that @math vertices suffice.