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, β= Θ(log 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(log 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(log tw), which is tight. As corollaries, we obtain an exponential improvement in dependency on treewidth in a host of algorithmic applications: O(√ log n · log(tw)) flow-cut gap, max flow-min multicut ratio of O(log(tw)), an O(log(tw)) approximation for the 0-extension problem, an O(log n)_∞ embedding with distortion O(log tw), and an O(log tw) bound for integrality gap for the uniform sparsest cut.