Scattering and Sparse Partitions, and their Applications
share
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. [STOC05] constructed a solution for the Universal Steiner Tree problem (and also Universal TSP) with stretch O(τσ^2log_τ 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.
READ FULL TEXT