Optimal Padded Decomposition For Bounded Treewidth Graphs

A (β, δ, Δ) -padded decomposition of an edge-weighted graph G = (V, E, w) is a stochastic decomposition into clusters of diameter at most Δ such that for every vertex v V, the probability that ballG (v, γΔ) is entirely contained in the cluster containing v is at least e^-βγ for every γ 0, δ. Padded decompositions have been studied for decades and have found numerous applications, including metric embedding, multicommodity flow-cut gap, multicut, and zero extension problems, to name a few. In these applications, parameter β, called the padding parameter, is the most important parameter since it decides either the distortion or the approximation ratios. For general graphs with n vertices, β= Θ (n). Klein, Plotkin, and Rao showed that Kᵣ-minor-free graphs have padding parameter β= O (r³), which is a significant improvement over general graphs when r is a constant. A long-standing conjecture is to construct a padded decomposition for Kᵣ-minor-free graphs with padding parameter β= O (r). Despite decades of research, the best-known result is β= O (r), even for graphs with treewidth at most r. In this work, we make significant progress toward the aforementioned conjecture by showing that graphs with treewidth tw admit a padded decomposition with padding parameter O (tw), which is tight. As corollaries, we obtain an exponential improvement in dependency on treewidth in a host of algorithmic applications: O (n (tw) ) flow-cut gap, max flow-min multicut ratio of O ( (tw) ), an O ( (tw) ) approximation for the 0-extension problem, an ^O (n) _ embedding with distortion O (tw), and an O (tw) bound for integrality gap for the uniform sparsest cut.