# Metric Embedding via Shortest Path Decompositions

Preprint · Ittai Abraham, Arnold Filtser, Anupam Gupta, Ofer Neiman

- Archive id: arxiv:1708.04073
- Published: 2017-08-14
- arXiv: https://arxiv.org/abs/1708.04073
- Source URL: https://arxiv.org/abs/1708.04073
- PDF: https://arxiv.org/pdf/1708.04073
- Provenance: arxiv

## 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 reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.