Planar and Minor-Free Metrics Embed into Metrics of Polylogarithmic Treewidth with Expected Multiplicative Distortion Arbitrarily Close to 1

Abstract

We prove that there is a randomized polynomial-time algorithm that given an edge-weighted graph $G$ excluding a fixed-minor $Q$ on $n$ vertices and an accuracy parameter $\epsilon >0$, constructs an edge-weighted graph~$H$ and an embedding $\eta :V(G)\to V(H)$ with the following properties: * For any constant size $Q$, the treewidth of $H$ is polynomial in ${\epsilon }^{-1}$, $\log n$, and the logarithm of the stretch of the distance metric in $G$. * The expected multiplicative distortion is $(1+\epsilon )$: for every pair of vertices $u,v$ of $G$, we have ${\mathrm{dist}}_H(\eta (u),\eta (v))\ge {\mathrm{dist}}_G(u,v)$ always and $\mathrm{Exp}[{\mathrm{dist}}_H(\eta (u),\eta (v))]\le (1+\epsilon ){\mathrm{dist}}_G(u,v)$. Our embedding is the first to achieve polylogarithmic treewidth of the host graph and comes close to the lower bound by Carroll and Goel, who showed that any embedding of a planar graph with $\mathcal{O}(1)$ expected distortion requires the host graph to have treewidth $\Omega (\log n)$. It also provides a unified framework for obtaining randomized quasi-polynomial-time approximation schemes for a variety of problems including network design, clustering or routing problems, in minor-free metrics where the optimization goal is the sum of selected distances. Applications include the capacitated vehicle routing problem, and capacitated clustering problems.