How to Protect Yourself from Threatening Skeletons: Optimal Padded Decompositions for Minor-Free Graphs

Roughly, a metric space has padding parameter β if for every ∆ > 0, there is a stochastic decomposition of the metric points into clusters of diameter at most ∆ such that every ball of radius γ∆ is contained in a single cluster with probability at least e -γβ . The padding parameter is an important characteristic of a metric space with vast algorithmic implications. In this paper we prove that the shortest path metric of every K r -minor-free graph has padding parameter O(log r), which is also tight. This resolves a long standing open question, and exponentially improves the previous bound. En route to our main result, we construct sparse covers for K r -minor-free graphs with improved parameters, and we prove a general reduction from sparse covers to padded decompositions.