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

Abstract

Roughly, a metric space has padding parameter ${\hat{I}}^2$ if for every $\hat{I}”>0$, there is a stochastic decomposition of the metric points into clusters of diameter at most $\hat{I}”$ such that every ball of radius ${\hat{I}}^3\hat{I}”$ is contained in a single cluster with probability at least $e^{-{\hat{I}}^3{\hat{I}}^2}$. 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.