2026-07-23T06:06:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23201 2025-10-02T12:42:49Z ddc:004 open_access

On Sparse Covers of Minor Free Graphs, Low Dimensional Metric Embeddings, and Other Applications Filtser, Arnold Sparse cover minor free graphs metric embeddings 𝓁_∞ oblivious buy-at-bulk Given a metric space (X,d_X), a (β,s,Δ)-sparse cover is a collection of clusters 𝒞 ⊆ P(X) with diameter at most Δ, such that for every point x ∈ X, the ball B_X(x,Δ/β) is fully contained in some cluster C ∈ 𝒞, and x belongs to at most s clusters in 𝒞. Our main contribution is to show that the shortest path metric of every K_r-minor free graphs admits (O(r),O(r²),Δ)-sparse cover, and for every ε > 0, (4+ε,O(1/ε)^r,Δ)-sparse cover (for arbitrary Δ > 0). We then use this sparse cover to show that every K_r-minor free graph embeds into 𝓁_∞^{Õ(1/ε)^{r+1}⋅log n} with distortion 3+ε (resp. into 𝓁_∞^{Õ(r²)⋅log n} with distortion O(r)). Further, among other applications, this sparse cover immediately implies an algorithm for the oblivious buy-at-bulk problem in fixed minor free graphs with the tight approximation factor O(log n) (previously nothing beyond general graphs was known). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Arnold Filtser 2025 Is Part Of LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2025.49 urn:nbn:de:0030-drops-232015 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.49 eng https://creativecommons.org/licenses/by/4.0/legalcode