{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,23]],"date-time":"2026-09-23T18:47:06Z","timestamp":1790189226763,"version":"4.1.0"},"reference-count":41,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1817\/17"],"award-info":[{"award-number":["1817\/17"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1536002"],"award-info":[{"award-number":["CCF-1536002"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1540541"],"award-info":[{"award-number":["CCF-1540541"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1617790"],"award-info":[{"award-number":["CCF-1617790"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006221","name":"United States - Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2015813"],"award-info":[{"award-number":["2015813"]}],"id":[{"id":"10.13039\/100006221","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2022,4]]},"abstract":"<jats:p>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 (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(k^{\\min\\{\\nicefrac{1}{p},\\nicefrac{1}{2}\\}})$-distortion embedding for graphs of SPD depth at most $k$. This result is asymptotically tight for any fixed $p&gt;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\\{\\nicefrac{1}{p},\\nicefrac{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.<\/jats:p>","DOI":"10.1137\/19m1296021","type":"journal-article","created":{"date-parts":[[2022,4,11]],"date-time":"2022-04-11T11:08:02Z","timestamp":1649675282000},"page":"290-314","source":"Crossref","is-referenced-by-count":4,"title":["Metric Embedding via Shortest Path Decompositions"],"prefix":"10.1137","volume":"51","author":[{"given":"Ittai","family":"Abraham","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9578-9304","authenticated-orcid":true,"given":"Arnold","family":"Filtser","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Anupam","family":"Gupta","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ofer","family":"Neiman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2022,4,11]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2011.08.003"},{"key":"atypb2","first-page":"20","author":"Abraham I.","year":"2015","journal-title":"NJ"},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"I. Abraham and C. Gavoille,\n                      Object location using path separators\n                      , in Proceedings of the Twenty-Fifth Annual ACM Symposium on Principles of Distributed Computing, PODC 2006, Denver, CO, ACM, pp. 188-197,https:\/\/doi.org\/10.1145\/1146381.1146411.","DOI":"10.1145\/1146381.1146411"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1137\/17M1112406"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(86)90026-2"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.24033\/bsmf.1997"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1145\/2783434"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.05.038"},{"key":"atypb9","first-page":"1","author":"Bodlaender H. L.","year":"1992","journal-title":"Heidelberg"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1007\/BF02776078"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480102417379"},{"key":"atypb12","first-page":"761","author":"Chakrabarti A.","year":"2008","journal-title":"PA"},{"key":"atypb13","first-page":"1945","author":"Filtser A.","year":"2020","journal-title":"Philadelphia"},{"key":"atypb14","unstructured":"A. Filtser,\n                      Scattering and sparse partitions, and their applications\n                      , in Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, Saarbr\u00fccken, Germany (Virtual Conference), A. Czumaj, A. Dawar, and E. Merelli, eds., Leibniz International Proceedings in Informatics (LIPIcs) 168, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2020, 47,https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2020.47."},{"key":"atypb15","first-page":"534","author":"Gupta A.","year":"2003","journal-title":"MA"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702409927"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-004-0015-x"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/026\/737400"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-011-9359-3"},{"key":"atypb20","first-page":"386","author":"Jia L.","year":"2005","journal-title":"ACM"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1142\/S1793525309000114"},{"key":"atypb22","first-page":"645","author":"Kamma L.","year":"2016","journal-title":"Algorithmica"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-012-0157-9"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-005-0527-6"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(93)90171-J"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200757"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-004-0473-8"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-009-9172-4"},{"key":"atypb29","first-page":"193","author":"Lee J. R.","year":"2010","journal-title":"Philadelphia"},{"key":"atypb30","doi-asserted-by":"crossref","unstructured":"J. R. Lee and A. Sidiropoulos,\n                      Near-optimal distortion bounds for embedding doubling spaces into l\\(_1\\)\n                      , in Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, ACM, 2011, pp. 765-772,https:\/\/doi.org\/10.1145\/1993636.1993737.","DOI":"10.1145\/1993636.1993737"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-013-2685-8"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1007\/BF02785579"},{"key":"atypb33","unstructured":"J. Matou\u0161ek,\n                      Lecture Notes on Metric Embeddings\n                      , Technical report, 2013,https:\/\/kam.mff.cuni.cz\/ matousek\/ba-a4.pdf."},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(86)90030-9"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.4171\/JEMS\/362"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-002-2813-5"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(81)80012-3"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-007-9047-5"},{"key":"atypb39","first-page":"300","author":"Rao S.","year":"1999","journal-title":"Miami Beach, FL"},{"key":"atypb40","first-page":"81","author":"Spielman D. A.","year":"2004","journal-title":"Chicago"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1145\/1039488.1039493"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/19M1296021","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:35:15Z","timestamp":1787337315000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/19M1296021"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4]]},"references-count":41,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,4]]}},"alternative-id":["10.1137\/19M1296021"],"URL":"https:\/\/doi.org\/10.1137\/19m1296021","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,4]]}}}