Metric embedding via shortest path decompositions

DOI10.1145/3188745.3188808MaRDI QIDQ5230353zbMATH OpenOpenAlexFDO

Authors Ittai Abraham, Arnold Filtser, Anupam Gupta, Ofer Neiman

Publication date 22 August 2019

Published in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1708.04073

zbMATH Keywords

metric embeddingsnormed spacespathwidthshortest path decompositiontreewidt

Mathematics Subject Classification ID

Embeddings of discrete metric spaces into Banach spaces; applications in topology and computer science (46B85) Graph theory (including graph drawing) in computer science (68R10) Metric embeddings as related to computational problems and algorithms (68R12) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: We study the problem of embedding shortest-path metrics of weighted graphs into $el{l}_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^{minfrac1p,frac12})$-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 $el{l}_p$ with distortion $O(k^{minfrac1p,frac12})$. 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(logn)$ to give a new proof that any planar graph embeds into $el{l}_1$ with distortion $O(sqrtlogn)$. Our approach also gives new results for graphs with bounded treewidth, and for graphs excluding a fixed minor.

Recommendations

• Algorithms for low-distortion embeddings into arbitrary 1-dimensional spaces
• On average distortion of embedding metrics into the line and into l₁
• Pathwidth, trees, and random embeddings
• A treehouse with custom windows: minimum distortion embeddings into bounded treewidth graphs
• Bandwidth and low dimensional embedding

Cited in

(13)

• Pathwidth, trees, and random embeddings
• Bandwidth and low dimensional embedding
• Optimal Embedding into Star Metrics
• Embedding Bounded Bandwidth Graphs into ℓ1
• Bandwidth and low dimensional embedding
• Metric Embedding via Shortest Path Decompositions
• Lossless prioritized embeddings
• Covering Metric Spaces by Few Trees
• Algorithms – ESA 2004
• Corrigendum: Metric Embedding via Shortest Path Decompositions
• Labelings vs. embeddings: on distributed and prioritized representations of distances
• Factorization and pseudofactorization of weighted graphs
• Scattering and sparse partitions, and their applications

This page was built for publication: Metric embedding via shortest path decompositions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5230353)