Back to Search
Start Over
METRIC EMBEDDING VIA SHORTEST PATH DECOMPOSITIONS.
- Source :
-
SIAM Journal on Computing . 2022, Vol. 51 Issue 2, p290-314. 25p. - Publication Year :
- 2022
-
Abstract
- We study the problem of embedding shortest-path metrics of weighted graphs into ℓ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 (SPD) depth is inductively defined: A (weighed) path graph has 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(kmin{1/p,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 ℓp with distortion O(kmin{1/p,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 ℓ1 with distortion O(√ log n). Our approach also gives new results for graphs with bounded treewidth, and for graphs excluding a fixed minor. [ABSTRACT FROM AUTHOR]
- Subjects :
- *PLANAR graphs
*WEIGHTED graphs
*EXPONENTIAL sums
Subjects
Details
- Language :
- English
- ISSN :
- 00975397
- Volume :
- 51
- Issue :
- 2
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Computing
- Publication Type :
- Academic Journal
- Accession number :
- 156540339
- Full Text :
- https://doi.org/10.1137/19M1296021