Arnold Filtser, Bar-Ilan University

Abstract

A partition P of a weighted graph G is (sigma, tau, Delta)-sparse if every cluster has diameter at most Delta, and every ball of radius Delta/sigma intersects at most tau clusters. Similarly, P is (sigma, tau, Delta)-scattering if instead for balls we require that every shortest path of length at most Delta/sigma intersects at most tau clusters. Given a graph G that admits a (sigma, tau, Delta)-sparse partition for all Delta>0, Jia et al. [STOC05] constructed a solution for the Universal Steiner Tree problem (and also Universal TSP) with stretch O(tau sigma^2 log_tau n).

Given a graph G that admits a (sigma, tau, Delta)-scattering partition for all Delta>0, we construct a solution for the Steiner Point Removal problem with stretch O( tau^3 sigma^3).

We then construct sparse and scattering partitions for various different graph families, receiving new results for the Universal Steiner Tree and Steiner Point Removal problems.