COPS, ROBBERS, and threatening skeletons: Padded decomposition for minor-free graphs

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

Research output: Contribution to journalArticlepeer-review


We prove that any graph excluding Kr as a minor 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 removing 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-minor-free graphs, O(k) for treewidth-k graphs, and O(log g) for graphs with (Euler) genus g.

Original languageEnglish (US)
Pages (from-to)1120-1145
Number of pages26
JournalSIAM Journal on Computing
Issue number3
StatePublished - 2019


  • Cops and robber
  • Excluded minor
  • Padded decomposition

ASJC Scopus subject areas

  • General Computer Science
  • General Mathematics


Dive into the research topics of 'COPS, ROBBERS, and threatening skeletons: Padded decomposition for minor-free graphs'. Together they form a unique fingerprint.

Cite this