2026-07-23T22:21:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12454 2024-03-06T10:50:11Z ddc:004 open_access

Scattering and Sparse Partitions, and Their Applications Filtser, Arnold Scattering partitions sparse partitions sparse covers Steiner point removal Universal Steiner tree Universal TSP A partition 𝒫 of a weighted graph G is (σ,τ,Δ)-sparse if every cluster has diameter at most Δ, and every ball of radius Δ/σ intersects at most τ clusters. Similarly, 𝒫 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(τσ²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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Arnold Filtser 2020 Is Part Of LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2020.47 urn:nbn:de:0030-drops-124547 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.47 eng https://creativecommons.org/licenses/by/3.0/legalcode