{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:28:09Z","timestamp":1750220889373,"version":"3.41.0"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2019,12,16]],"date-time":"2019-12-16T00:00:00Z","timestamp":1576454400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2020,3,31]]},"abstract":"\n Given metric spaces (\n X<\/jats:italic>\n ,\n D<\/jats:italic>\n \n X<\/jats:italic>\n <\/jats:sub>\n ) and (\n Y<\/jats:italic>\n ,\n D<\/jats:italic>\n \n Y<\/jats:italic>\n <\/jats:sub>\n ), an\n embedding<\/jats:italic>\n F<\/jats:italic>\n :\n X<\/jats:italic>\n \u2192\n Y<\/jats:italic>\n is an injective mapping from\n X<\/jats:italic>\n to\n Y<\/jats:italic>\n .\n Expansion<\/jats:italic>\n e<\/jats:italic>\n \n F<\/jats:italic>\n <\/jats:sub>\n and\n contraction<\/jats:italic>\n c<\/jats:italic>\n \n F<\/jats:italic>\n <\/jats:sub>\n of an embedding\n F<\/jats:italic>\n :\n X<\/jats:italic>\n \u2192\n Y<\/jats:italic>\n are defined as\n <\/jats:p>\n \n e<\/jats:italic>\n \n F<\/jats:italic>\n <\/jats:sub>\n = max\n \n x<\/jats:italic>\n ;\n 1<\/jats:sub>\n ,\n x<\/jats:italic>\n 2<\/jats:sub>\n (\u2260\n x<\/jats:italic>\n 1<\/jats:sub>\n ) \u2208\n X<\/jats:italic>\n <\/jats:sub>\n D<\/jats:italic>\n \n Y<\/jats:italic>\n <\/jats:sub>\n (\n F<\/jats:italic>\n (\n x<\/jats:italic>\n 1<\/jats:sub>\n ),\n F<\/jats:italic>\n (\n x<\/jats:italic>\n 2<\/jats:sub>\n ))\/\n D<\/jats:italic>\n \n X<\/jats:italic>\n <\/jats:sub>\n (\n x<\/jats:italic>\n 1<\/jats:sub>\n ,\n x<\/jats:italic>\n 2<\/jats:sub>\n ) and\n c<\/jats:italic>\n \n F<\/jats:italic>\n <\/jats:sub>\n = max\n \n x<\/jats:italic>\n 1<\/jats:sub>\n ,\n x<\/jats:italic>\n 2<\/jats:sub>\n (\u2260\n x<\/jats:italic>\n 1<\/jats:sub>\n ) \u2208\n X<\/jats:italic>\n <\/jats:sub>\n D<\/jats:italic>\n \n X<\/jats:italic>\n <\/jats:sub>\n (\n x<\/jats:italic>\n 1<\/jats:sub>\n ,\n x<\/jats:italic>\n 2<\/jats:sub>\n )\/\n D<\/jats:italic>\n \n Y<\/jats:italic>\n <\/jats:sub>\n (\n F<\/jats:italic>\n (\n x<\/jats:italic>\n 1<\/jats:sub>\n ),\n F<\/jats:italic>\n (\n x<\/jats:italic>\n 2<\/jats:sub>\n )),\n <\/jats:p>\n \n respectively, and\n distortion<\/jats:italic>\n d<\/jats:italic>\n \n F<\/jats:italic>\n <\/jats:sub>\n is defined as\n d<\/jats:italic>\n \n F<\/jats:italic>\n <\/jats:sub>\n =\n e<\/jats:italic>\n \n F<\/jats:italic>\n <\/jats:sub>\n \u22c5\n c<\/jats:italic>\n \n F<\/jats:italic>\n <\/jats:sub>\n . Observe that\n d<\/jats:italic>\n \n F<\/jats:italic>\n <\/jats:sub>\n \u2265 1. An embedding\n F<\/jats:italic>\n :\n X<\/jats:italic>\n \u2192\n Y<\/jats:italic>\n is\n noncontracting<\/jats:italic>\n if\n c<\/jats:italic>\n \n F<\/jats:italic>\n <\/jats:sub>\n \u2264 1. When\n d<\/jats:italic>\n =1, then\n F<\/jats:italic>\n is\n isometry<\/jats:italic>\n .\n <\/jats:p>\n \n The M\n etric<\/jats:sc>\n E\n mbedding<\/jats:sc>\n problem takes as input two metric spaces (\n X<\/jats:italic>\n ,\n D<\/jats:italic>\n \n X<\/jats:italic>\n <\/jats:sub>\n ) and (\n Y<\/jats:italic>\n ,\n D<\/jats:italic>\n \n Y<\/jats:italic>\n <\/jats:sub>\n ), and a positive integer\n d<\/jats:italic>\n . The objective is to determine whether there is an embedding\n F<\/jats:italic>\n :\n X<\/jats:italic>\n \u2192\n Y<\/jats:italic>\n such that\n d<\/jats:italic>\n \n F<\/jats:italic>\n <\/jats:sub>\n \u2264\n d<\/jats:italic>\n . Such an embedding is called a\n distortion d embedding<\/jats:italic>\n . The bijective M\n etric<\/jats:sc>\n E\n mbedding<\/jats:sc>\n problem is a special case of the M\n etric<\/jats:sc>\n E\n mbedding<\/jats:sc>\n problem where \u2223\n X<\/jats:italic>\n \u2223 = \u2223\n Y<\/jats:italic>\n \u2223. In parameterized complexity, the M\n etric<\/jats:sc>\n E\n mbedding<\/jats:sc>\n problem, in full generality, is known to be W-hard and, therefore, not expected to have an FPT algorithm. In this article, we consider the G\n en<\/jats:sc>\n -G\n raph<\/jats:sc>\n M\n etric<\/jats:sc>\n E\n mbedding<\/jats:sc>\n problem, where the two metric spaces are graph metrics. We explore the extent of tractability of the problem in the parameterized complexity setting. We determine whether an unweighted graph metric (\n G<\/jats:italic>\n ,\n D<\/jats:italic>\n \n G<\/jats:italic>\n <\/jats:sub>\n ) can be embedded, or bijectively embedded, into another unweighted graph metric (\n H<\/jats:italic>\n ,\n D<\/jats:italic>\n \n H<\/jats:italic>\n <\/jats:sub>\n ), where the graph\n H<\/jats:italic>\n has low structural complexity. For example,\n H<\/jats:italic>\n is a cycle, or\n H<\/jats:italic>\n has bounded treewidth or bounded connected treewidth. The parameters for the algorithms are chosen from the upper bound\n d<\/jats:italic>\n on distortion, bound \u0394 on the maximum degree of\n H<\/jats:italic>\n , treewidth \u03b1 of\n H<\/jats:italic>\n , and connected treewidth \u03b1\n \n c<\/jats:italic>\n <\/jats:sub>\n of\n H<\/jats:italic>\n .\n <\/jats:p>\n \n Our general approach to these problems can be summarized as trying to understand the behavior of the shortest paths in\n G<\/jats:italic>\n under a low-distortion embedding into\n H<\/jats:italic>\n , and the structural relation the mapping of these paths has to shortest paths in\n H<\/jats:italic>\n .\n <\/jats:p>","DOI":"10.1145\/3369933","type":"journal-article","created":{"date-parts":[[2019,12,17]],"date-time":"2019-12-17T13:32:58Z","timestamp":1576589578000},"page":"1-41","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["FPT Algorithms for Embedding into Low-Complexity Graphic Metrics"],"prefix":"10.1145","volume":"12","author":[{"given":"Arijit","family":"Ghosh","sequence":"first","affiliation":[{"name":"Indian Statistical Institute, Kolkata, India"}]},{"given":"Sudeshna","family":"Kolay","sequence":"additional","affiliation":[{"name":"Ben-Gurion University of the Negev, Israel"}]},{"given":"Gopinath","family":"Mishra","sequence":"additional","affiliation":[{"name":"Indian Statistical Institute, Kolkata, India"}]}],"member":"320","published-online":{"date-parts":[[2019,12,16]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2011.08.003"},{"volume-title":"Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC\u201905)","author":"Badoiu M.","key":"e_1_2_1_2_1","unstructured":"M. Badoiu , J. Chuzhoy , P. Indyk , and A. Sidiropoulos . 2005. Low-distortion embeddings of general metrics into the line . In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC\u201905) . 225--233. M. Badoiu, J. Chuzhoy, P. Indyk, and A. Sidiropoulos. 2005. Low-distortion embeddings of general metrics into the line. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC\u201905). 225--233."},{"volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201905)","author":"Badoiu M.","key":"e_1_2_1_3_1","unstructured":"M. Badoiu , K. Dhamdhere , A. Gupta , Y. Rabinovich , H. R\u00e4cke , R. Ravi , and A. Sidiropoulos . 2005. Approximation algorithms for low-distortion embeddings into low-dimensional spaces . In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201905) . 119--128. M. Badoiu, K. Dhamdhere, A. Gupta, Y. Rabinovich, H. R\u00e4cke, R. Ravi, and A. Sidiropoulos. 2005. Approximation algorithms for low-distortion embeddings into low-dimensional spaces. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201905). 119--128."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/874062.875536"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02776078"},{"key":"e_1_2_1_6_1","unstructured":"T. Carpenter F. V. Fomin D. Lokshtanov S. Saurabh and A. Sidiropoulos. 2017. Algorithms for low-distortion embeddings into arbitrary 1-dimensional spaces. CoRR abs\/1712.06747 (2017). http:\/\/arxiv.org\/abs\/1712.06747. T. Carpenter F. V. Fomin D. Lokshtanov S. Saurabh and A. Sidiropoulos. 2017. Algorithms for low-distortion embeddings into arbitrary 1-dimensional spaces. CoRR abs\/1712.06747 (2017). http:\/\/arxiv.org\/abs\/1712.06747."},{"volume-title":"Proceedings of the 34th International Symposium on Computational Geometry (SoCG\u201918)","author":"Carpenter T.","key":"e_1_2_1_7_1","unstructured":"T. Carpenter , F. V. Fomin , D. Lokshtanov , S. Saurabh , and A. Sidiropoulos . 2018. Algorithms for low-distortion embeddings into arbitrary 1-dimensional spaces . In Proceedings of the 34th International Symposium on Computational Geometry (SoCG\u201918) . 21:1--21:14. T. Carpenter, F. V. Fomin, D. Lokshtanov, S. Saurabh, and A. Sidiropoulos. 2018. Algorithms for low-distortion embeddings into arbitrary 1-dimensional spaces. In Proceedings of the 34th International Symposium on Computational Geometry (SoCG\u201918). 21:1--21:14."},{"volume-title":"[n.d.]. Parameterized Algorithms","author":"Cygan M.","key":"e_1_2_1_8_1","unstructured":"M. Cygan , F. V. Fomin , L. Kowalik , D. Lokshtanov , D. Marx , M. Pilipczuk , M. Pilipczuk , and S. Saurabh . [n.d.]. Parameterized Algorithms . Springer . M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. [n.d.]. Parameterized Algorithms. Springer."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-016-3516-5"},{"volume-title":"Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC\u201903)","author":"Fakcharoenphol J.","key":"e_1_2_1_10_1","unstructured":"J. Fakcharoenphol , S. Rao , and K. Talwar . 2003. A tight bound on approximating arbitrary metrics by tree metrics . In Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC\u201903) . 448--455. J. Fakcharoenphol, S. Rao, and K. Talwar. 2003. A tight bound on approximating arbitrary metrics by tree metrics. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC\u201903). 448--455."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2489789"},{"key":"e_1_2_1_12_1","unstructured":"J. Flum and M. Grohe. 2006. Parameterized Complexity Theory. Springer. J. Flum and M. Grohe. 2006. Parameterized Complexity Theory. Springer."},{"volume-title":"Proceedings of the 44th Annual Symposium on Foundations of Computer Science (FOCS\u201903)","author":"Gupta A.","key":"e_1_2_1_13_1","unstructured":"A. Gupta , R. Krauthgamer , and J. R. Lee . 2003. Bounded geometries, fractals, and low-distortion embeddings . In Proceedings of the 44th Annual Symposium on Foundations of Computer Science (FOCS\u201903) . 534--543. A. Gupta, R. Krauthgamer, and J. R. Lee. 2003. Bounded geometries, fractals, and low-distortion embeddings. In Proceedings of the 44th Annual Symposium on Foundations of Computer Science (FOCS\u201903). 534--543."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-004-0015-x"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2001.959878"},{"key":"e_1_2_1_16_1","volume-title":"Conference in Modern Analysis and Probability","author":"Johnson W.","year":"1982","unstructured":"W. Johnson and J. Lindenstrauss . 1984. Extensions of Lipschitz mappings into a Hilbert space . In Conference in Modern Analysis and Probability ( New Haven, Conn. , 1982 ). Contemporary Mathematics, Vol. 26. American Mathematical Society, 189--206. W. Johnson and J. Lindenstrauss. 1984. Extensions of Lipschitz mappings into a Hilbert space. In Conference in Modern Analysis and Probability (New Haven, Conn., 1982). Contemporary Mathematics, Vol. 26. American Mathematical Society, 189--206."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/080712921"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200757"},{"key":"e_1_2_1_19_1","unstructured":"J. Matou\u0161ek. 2013. Lecture Notes on Metric Embeddings. Retrieved from http:\/\/kam.mff.cuni.cz\/ matousek\/ba-a4.pdf. J. Matou\u0161ek. 2013. Lecture Notes on Metric Embeddings. Retrieved from http:\/\/kam.mff.cuni.cz\/ matousek\/ba-a4.pdf."},{"volume-title":"Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS\u201915)","author":"Nayyeri A.","key":"e_1_2_1_20_1","unstructured":"A. Nayyeri and B. Raichel . 2015. Reality distortion: Exact and approximate algorithms for embedding into the line . In Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS\u201915) . 729--747. A. Nayyeri and B. Raichel. 2015. Reality distortion: Exact and approximate algorithms for embedding into the line. In Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS\u201915). 729--747."},{"volume-title":"Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201917)","author":"Nayyeri A.","key":"e_1_2_1_21_1","unstructured":"A. Nayyeri and B. Raichel . 2017. A treehouse with custom windows: Minimum distortion embeddings into bounded treewidth graphs . In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201917) . 724--736. A. Nayyeri and B. Raichel. 2017. A treehouse with custom windows: Minimum distortion embeddings into bounded treewidth graphs. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201917). 724--736."}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3369933","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3369933","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:44:27Z","timestamp":1750203867000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3369933"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,16]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,3,31]]}},"alternative-id":["10.1145\/3369933"],"URL":"https:\/\/doi.org\/10.1145\/3369933","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2019,12,16]]},"assertion":[{"value":"2018-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-12-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}