TY - GEN

T1 - Cops, robbers, and threatening skeletons

T2 - 4th Annual ACM Symposium on Theory of Computing, STOC 2014

AU - Abraham, Ittai

AU - Gavoille, Cyril

AU - Gupta, Anupam

AU - Neiman, Ofer

AU - Talwar, Kunal

PY - 2014

Y1 - 2014

N2 - 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 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(r2) for Kr-free graphs, O(κ) for treewidth-κ graphs, and O(log g) for graphs with genus g.

AB - 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 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(r2) for Kr-free graphs, O(κ) for treewidth-κ graphs, and O(log g) for graphs with genus g.

KW - Cops and robbers

KW - Excluded minor

KW - Padded decomposition

UR - http://www.scopus.com/inward/record.url?scp=84904289695&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84904289695&partnerID=8YFLogxK

U2 - 10.1145/2591796.2591849

DO - 10.1145/2591796.2591849

M3 - Conference contribution

AN - SCOPUS:84904289695

SN - 9781450327107

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 79

EP - 88

BT - STOC 2014 - Proceedings of the 2014 ACM Symposium on Theory of Computing

PB - Association for Computing Machinery

Y2 - 31 May 2014 through 3 June 2014

ER -