Planar and Minor-Free Metrics Embed into Metrics of Polylogarithmic Treewidth with Expected Multiplicative Distortion Arbitrarily Close to 1*
Vincent Cohen-Addad, Hung Le, Marcin Pilipczuk, Michał Pilipczuk · 2023
We prove that there is a randomized polynomialtime algorithm that given an edge-weighted graph G excluding a fixed-minor Q on n vertices and an accuracy parameter $\varepsilon\gt$ 0, constructs an edge-weighted graph H and an embedding $\eta: V(G) \rightarrow V(H)$ with the following properties:•For any constant size Q, the treewidth of H is polynomial in $\varepsilon^{-1}, \log n$, and the logarithm of the stretch of the distance metric in G.•The expected multiplicative distortion is $(1+\varepsilon)$: for every pair of vertices $u, v$ of G, we have $\operatorname{dist}_{H}(\eta(u), \eta(v)) \geqslant \operatorname{dist}_{G}(u, v)$ always and $\mathbb{E}\left[\operatorname{dist}_{H}(\eta(u), \eta(v))\right] \leqslant(1+\varepsilon) \operatorname{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.