How to Protect Yourself from Threatening Skeletons: Optimal Padded Decompositions for Minor-Free Graphs

2025/03/31 by Jonathan Conroy, Arnold Filtser, Conroy, Jonathan +1 · 1 voice · 2 citations
#cs.DS

paper · pdf · doi:10.48550/arxiv.2504.00278

Abstract

Roughly, a metric space has padding parameter β if for every Δ>0, there is a stochastic decomposition of the metric points into clusters of diameter at most Δ such that every ball of radius γΔ is contained in a single cluster with probability at least e^-γβ. The padding parameter is an important characteristic of a metric space with vast algorithmic implications. In this paper we prove that the shortest path metric of every K_r-minor-free graph has padding parameter O(log r), which is also tight. This resolves a long standing open question, and exponentially improves the previous bound. En route to our main result, we construct sparse covers for K_r-minor-free graphs with improved parameters, and we prove a general reduction from sparse covers to padded decompositions.

Cited by

• Separator Theorem for Minor-Free Graphs in Linear Time
• Tree Embedding in High Dimensions: Dynamic and Massively Parallel

Discussions

• Jonathan Conroy and Arnold Filtser have recently solved the padded decomposition problem for minor-free graphs, one of my favorite open problems. Congratulations to both! Their paper here: arxiv.org/a [bsky, 5 points, 0 comments]

Related

• Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs
• Optimal Padded Decomposition For Bounded Treewidth Graphs
• On Sparse Covers of Minor Free Graphs, Low Dimensional Metric Embeddings, and other applications
• On Strong Diameter Padded Decompositions
• Metric Decompositions of Path-Separable Graphs