{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T00:23:55Z","timestamp":1760142235235,"version":"build-2065373602"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"accepted":{"date-parts":[[2025,8,17]]},"abstract":"<jats:p>A $(\u03b2,\u03b4,\u0394)$-padded decomposition of an edge-weighted graph $G = (V,E,w)$ is a stochastic decomposition into clusters of diameter at most $\u0394$ such that for every vertex $v\\in V$, the probability that $\\rm{ball}_G(v,\u03b3\u0394)$ is entirely contained in the cluster containing $v$ is at least $e^{-\u03b2\u03b3}$ for every $\u03b3\\in [0,\u03b4]$. 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 $\u03b2$, 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, $\u03b2= \u0398(\\log n)$. Klein, Plotkin, and Rao showed that $K_r$-minor-free graphs have padding parameter $\u03b2= O(r^3)$, 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_r$-minor-free graphs with padding parameter $\u03b2= O(\\log r)$. Despite decades of research, the best-known result is $\u03b2= 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 $\\rm{tw}$ admit a padded decomposition with padding parameter $O(\\log \\rm{tw})$, which is tight. As corollaries, we obtain an exponential improvement in dependency on treewidth in a host of algorithmic applications: $O(\\sqrt{ \\log n \\cdot \\log(\\rm{tw})})$ flow-cut gap, max flow-min multicut ratio of $O(\\log(\\rm{tw}))$, an $O(\\log(\\rm{tw}))$ approximation for the 0-extension problem, an $\\ell^{O(\\log n)}_\\infty$ embedding with distortion $O(\\log \\rm{tw})$, and an $O(\\log \\rm{tw})$ bound for integrality gap for the uniform sparsest cut.<\/jats:p><jats:p>39 pages. This is the TheoretiCS journal version<\/jats:p>","DOI":"10.46298\/theoretics.25.22","type":"journal-article","created":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T07:50:15Z","timestamp":1760082615000},"source":"Crossref","is-referenced-by-count":0,"title":["Optimal Padded Decomposition For Bounded Treewidth Graphs"],"prefix":"10.46298","volume":"Volume 4","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9578-9304","authenticated-orcid":false,"given":"Arnold","family":"Filtser","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0076-6308","authenticated-orcid":false,"given":"Tobias","family":"Friedrich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Davis","family":"Issac","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8634-6237","authenticated-orcid":false,"given":"Nikhil","family":"Kumar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8223-9944","authenticated-orcid":false,"given":"Hung","family":"Le","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4370-5145","authenticated-orcid":false,"given":"Nadym","family":"Mallek","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0378-1458","authenticated-orcid":false,"given":"Ziena","family":"Zeif","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2025,10,10]]},"container-title":["TheoretiCS"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/arxiv.org\/pdf\/2407.12230v3","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/arxiv.org\/pdf\/2407.12230v3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T07:50:15Z","timestamp":1760082615000},"score":1,"resource":{"primary":{"URL":"https:\/\/theoretics.episciences.org\/14714"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,10]]},"references-count":0,"URL":"https:\/\/doi.org\/10.46298\/theoretics.25.22","relation":{"has-preprint":[{"id-type":"arxiv","id":"2407.12230v2","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"2407.12230","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.2407.12230","asserted-by":"subject"}]},"ISSN":["2751-4838"],"issn-type":[{"value":"2751-4838","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,10]]},"article-number":"14714"}}