Scattering and Sparse Partitions, and their Applications

A partition $\mathcal{P}$ of a weighted graph $G$ is $(σ,τ,Δ)$-sparse if every cluster has diameter at most $Δ$, and every ball of radius $Δ/σ$ intersects at most $τ$ clusters. Similarly, $\mathcal{P}$ is $(σ,τ,Δ)$-scattering if instead for balls we require that every shortest path of length at most $Δ/σ$ intersects at most $τ$ clusters. Given a graph $G$ that admits a $(σ,τ,Δ)$-sparse partition for all $Δ>0$, Jia et al. [STOC05] constructed a solution for the Universal Steiner Tree problem (and also Universal TSP) with stretch $O(τσ^2\log_τn)$. Given a graph $G$ that admits a $(σ,τ,Δ)$-scattering partition for all $Δ>0$, we construct a solution for the Steiner Point Removal problem with stretch $O(τ^3σ^3)$. We then construct sparse and scattering partitions for various different graph families, receiving many new results for the Universal Steiner Tree and Steiner Point Removal problems.