Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs

Ittai Abraham, Cyril Gavoille, Anupam Gupta, Ofer Neiman, and Kunal Talwar

Abstract

We prove that any graph excluding Kr as a minor has can be partitioned into clusters of diameter at most Δ while removing at most O(r/Δ) 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 to remove O(r2/Δ) fraction of the edges.

Our result is obtained by a new approach to relate 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 excluded-minor graphs 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(r2) for

Kr-free graphs, padding O(k) for graphs with treewidth

k, and padding O(log g) for graphs with genus g.

Details

Publication typeInproceedings
Published inSTOC '14 Proceedings of the 46th symposium on Theory of Computing
> Publications > Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs