Ittai Abraham, Cyril Gavoille, Anupam Gupta, Ofer Neiman, and Kunal Talwar
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.
|Published in||STOC '14 Proceedings of the 46th symposium on Theory of Computing|