ProV Logo
0
Cops, Robbers, and Threatening Skeletons...
Abraham, Ittai...

Free

Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs by Abraham, Ittai ( Author )
Lemonjar Open Access
Australian National University
04-08-2023
We prove that any graph excluding $K_r$ as a minor has 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 to remove $O(r^2/\Delta)$ 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(r^2)$ for $K_r$-free graphs, padding $O(k)$ for graphs with treewidth $k$, and padding $O(\log g)$ for graphs with genus $g$.
-
Article
pdf
29.34 KB
English
-
MYR 0.01
-
http://arxiv.org/abs/1311.3048
Share this eBook