Metric Embedding via Shortest Path Decompositions

Abstract

We study the problem of embedding shortest-path metrics of weighted graphs into $\ell_p$ spaces. We introduce a new embedding technique based on low-depth decompositions of a graph via shortest paths. The notion of Shortest Path Decomposition depth is inductively defined: A (weighed) path graph has shortest path decomposition (SPD) depth $1$. General graph has an SPD of depth $k$ if it contains a shortest path whose deletion leads to a graph, each of whose components has SPD depth at most $k-1$. In this paper we give an $O(k^{\min\{\frac{1}{p},\frac{1}{2}\}})$-distortion embedding for graphs of SPD depth at most $k$. This result is asymptotically tight for any fixed $p>1$, while for $p=1$ it is tight up to second order terms. As a corollary of this result, we show that graphs having pathwidth $k$ embed into $\ell_p$ with distortion $O(k^{\min\{\frac{1}{p},\frac{1}{2}\}})$. For $p=1$, this improves over the best previous bound of Lee and Sidiropoulos that was exponential in $k$; moreover, for other values of $p$ it gives the first embeddings whose distortion is independent of the graph size $n$. Furthermore, we use the fact that planar graphs have SPD depth $O(\log n)$ to give a new proof that any planar graph embeds into $\ell_1$ with distortion $O(\sqrt{\log n})$. Our approach also gives new results for graphs with bounded treewidth, and for graphs excluding a fixed minor.

Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.