Scattering and Sparse Partitions, and Their Applications

A partition \(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, \(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. constructed a solution for the Universal Steiner Tree problem (and also Universal TSP) with stretch \(O(τσ² 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(τ³σ³)\) . 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.