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.

Authors

• Jonathan Conroy
• Arnold Filtser

Keywords

• Minor-free graphs
• Padded decomposition
• Sparse cover