Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs
Ittai Abraham, Cyril Gavoille, Anupam Gupta, Ofer Neiman, Kunal Talwar · SIAM Journal on Computing · 2019
We prove that any graph excluding $K_r$ as a minor can be partitioned into clusters of diameter at most $\Delta$ while removing at most $O(r/\Delta)$ fraction of the edges. This improves over the results of Fakcharoenphol and Talwar, who, building on the work of Klein, Plotkin, and Rao, gave a partitioning that required removing $O(r^2/\Delta)$ fraction of the edges. Our result is obtained by a new approach that relates the topological properties (excluding a minor) of a graph to its geometric properties (the induced shortest path metric). Specifically, we show that techniques used by Andreae in his investigation of the cops and robbers game on graphs excluding a fixed minor can be used to construct padded decompositions of the metrics induced by such graphs. In particular, we get probabilistic partitions with padding parameter $O(r)$ and strong-diameter partitions with padding parameter $O(r^2)$ for $K_r$-minor-free graphs, $O(k)$ for treewidth-$k$ graphs, and $O(\log g)$ for graphs with (Euler) genus $g$.