{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:42:22Z","timestamp":1787341342456,"version":"build-2736575974"},"reference-count":40,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"name":"CMU-Microsoft Center for Computational Thinking"},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["523\/12"],"award-info":[{"award-number":["523\/12"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1016799"],"award-info":[{"award-number":["CCF-1016799"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1319811"],"award-info":[{"award-number":["CCF-1319811"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006221","name":"United States - Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2015813"],"award-info":[{"award-number":["2015813"]}],"id":[{"id":"10.13039\/100006221","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2019,1]]},"abstract":"<jats:p>We prove that any graph excluding $K_r$ as a minor 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 removing $O(r^2\/\\Delta)$ 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(r^2)$ for $K_r$-minor-free graphs, $O(k)$ for treewidth-$k$ graphs, and $O(\\log g)$ for graphs with (Euler) genus $g$.<\/jats:p>","DOI":"10.1137\/17m1112406","type":"journal-article","created":{"date-parts":[[2019,5,23]],"date-time":"2019-05-23T14:24:56Z","timestamp":1558621496000},"page":"1120-1145","source":"Crossref","is-referenced-by-count":25,"title":["Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs"],"prefix":"10.1137","volume":"48","author":[{"given":"Ittai","family":"Abraham","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Cyril","family":"Gavoille","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Anupam","family":"Gupta","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ofer","family":"Neiman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kunal","family":"Talwar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2019,5,23]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2011.08.003"},{"key":"atypb2","first-page":"1079","author":"Archer A.","year":"2004","journal-title":"New York"},{"key":"atypb3","first-page":"79","author":"Abraham I.","year":"2014","journal-title":"New York"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-010-9283-6"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(86)90026-2"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-1990-1065053-0"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1145\/4221.4227"},{"key":"atypb8","first-page":"184","author":"Bartal Y.","year":"1996","journal-title":"Washington, DC"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0049"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1145\/1706591.1706593"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2010.04.007"},{"key":"atypb12","first-page":"61","author":"Busch C.","year":"2007","journal-title":"New York"},{"key":"atypb13","first-page":"100","author":"\u00c9","year":"2010","journal-title":"Berlin"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701395978"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"R. Diestel,\n                      Graph Theory\n                      , Grad. Texts in Math. 173, 2nd ed., Springer-Verlag, New York, 2000.","DOI":"10.1007\/978-3-662-53622-3_7"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1137\/05064299X"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.011"},{"key":"atypb18","first-page":"36","author":"Fakcharoenphol J.","year":"2003","journal-title":"Berlin"},{"key":"atypb19","doi-asserted-by":"crossref","unstructured":"A. Gupta, R. Krauthgamer, and J. R. Lee,\n                      Bounded geometries, fractals, and low-distortion embeddings\n                      , in 16th Annual Symposium on Foundations of Computer Science, 2003, pp. 534-543.","DOI":"10.1109\/SFCS.2003.1238226"},{"key":"atypb20","doi-asserted-by":"crossref","unstructured":"G. R. Grimmett and D. R. Stirzaker,\n                      Probability and Random Processes\n                      , 3rd ed., Oxford University Press, New York, 2001.","DOI":"10.1093\/oso\/9780198572237.001.0001"},{"key":"atypb21","first-page":"281","author":"Gupta A.","year":"2013","journal-title":"New York"},{"key":"atypb22","first-page":"204","author":"Indyk P.","year":"2007","journal-title":"New York"},{"key":"atypb23","doi-asserted-by":"crossref","unstructured":"J. A. Kelner, J. R. Lee, G. N. Price, and S.H. Teng,\n                      Higher eigenvalues of graphs\n                      , in Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 2009, pp. 735-744.","DOI":"10.1109\/FOCS.2009.69"},{"key":"atypb24","first-page":"771","author":"Kawarabayashi K.-i.","year":"2008","journal-title":"Washington, DC"},{"key":"atypb25","first-page":"682","author":"Klein P. N.","year":"1993","journal-title":"New York"},{"key":"atypb26","unstructured":"J. R. Lee,\n                      Open Question Recap\n                      , 2013,http:\/\/tcsmath.wordpress.com\/2013\/02\/25\/open-question-recap\/."},{"key":"atypb27","first-page":"1117","author":"Lee J. R.","year":"2012","journal-title":"New York"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1007\/s00222-004-0400-5"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1007\/BF01303516"},{"key":"atypb30","first-page":"193","author":"Lee J. R.","year":"2010","journal-title":"New York"},{"key":"atypb31","doi-asserted-by":"crossref","unstructured":"J. Matou\u0161ek,\n                      Lectures on Discrete Geometry\n                      , Grad. Texts Math. 212, Springer-Verlag, New York, 2002.","DOI":"10.1007\/978-1-4613-0039-7"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1137\/S089548019529248X"},{"key":"atypb33","doi-asserted-by":"crossref","unstructured":"B. Mohar and C. Thomassen,\n                      Graphs on Surfaces\n                      , The Johns Hopkins University Press, Baltimore, 2001.","DOI":"10.56021\/9780801866890"},{"key":"atypb34","first-page":"462","author":"Plotkin S.","year":"1994","journal-title":"New York"},{"key":"atypb35","first-page":"456","author":"Rabinovich Y.","year":"2003","journal-title":"New York"},{"key":"atypb36","first-page":"300","author":"Rao S. B.","year":"1999","journal-title":"New York"},{"key":"atypb37","first-page":"221","author":"Reed B. A.","year":"1992","journal-title":"New York"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(03)00042-X"},{"key":"atypb39","doi-asserted-by":"crossref","unstructured":"A. Sidiropoulos,\n                      Optimal stochastic planarization\n                      , in Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science, 2010, pp. 163-170.","DOI":"10.1109\/FOCS.2010.23"},{"key":"atypb40","doi-asserted-by":"crossref","unstructured":"C. Wulff-Nilsen,\n                      Separator theorems for minor-free and shallow minor-free graphs with applications\n                      , in Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Soc., Los Alamitos, CA, 2011, pp. 37-46.","DOI":"10.1109\/FOCS.2011.15"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1112406","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:14:23Z","timestamp":1787339663000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1112406"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1]]},"references-count":40,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,1]]}},"alternative-id":["10.1137\/17M1112406"],"URL":"https:\/\/doi.org\/10.1137\/17m1112406","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1]]}}}