publication . Conference object . Other literature type . Preprint . Report . Article . 2014

Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs

Ittai Abraham; Cyril Gavoille; Anupam Gupta; Ofer Neiman; Kunal Talwar;
Open Access English
  • Published: 01 May 2014
  • Publisher: HAL CCSD
  • Country: France
Abstract
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 u...
Subjects
free text keywords: minor graph, graph decomposition, sparse partition, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 89999 Information and Computing Sciences not elsewhere classified, FOS: Computer and information sciences, Computer Science - Data Structures and Algorithms, minor, decomposition, General Mathematics, General Computer Science, Cluster (physics), Mathematics, Graph, Decomposition, Combinatorics
Funded by
EC| DIMENSION
Project
DIMENSION
The Role of Dimension in Metric Embedding
  • Funder: European Commission (EC)
  • Project Code: 303809
  • Funding stream: FP7 | SP3 | PEOPLE
,
NSF| AF: Small: Future Directions in Approximation Algorithms Research
Project
  • Funder: National Science Foundation (NSF)
  • Project Code: 1016799
  • Funding stream: Directorate for Computer & Information Science & Engineering | Division of Computing and Communication Foundations
,
NSF| AF: Small: Approximation Algorithms for Uncertain Environments and Graph Partitioning
Project
  • Funder: National Science Foundation (NSF)
  • Project Code: 1319811
  • Funding stream: Directorate for Computer & Information Science & Engineering | Division of Computing and Communication Foundations

[KLPT09] Jonathan A. Kelner, James R. Lee, Gregory N. Price, and Shang-Hua Teng. Higher eigenvalues of graphs. In FOCS, pages 735{744, 2009.

Philip N. Klein, Serge A. Plotkin, and Satish Rao. Excluded minors, network decomposition, and multicommodity ow. In STOC, pages 682{690, 1993.

James R. Lee. Open question recap, http://tcsmath.wordpress.com/2013/02/25/open-question-recap/.

2)s e (2s+1)h

Any information missing or wrong?Report an Issue