{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:22:51Z","timestamp":1750306971589,"version":"3.41.0"},"reference-count":16,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2013,11,1]],"date-time":"2013-11-01T00:00:00Z","timestamp":1383264000000},"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":[[2013,11]]},"abstract":"\n We study low-distortion embedding of metric spaces into the line, and more generally, into the shortest path metric of trees, from the parameterized complexity perspective. Let\n M<\/jats:italic>\n =\n M<\/jats:italic>\n (\n G<\/jats:italic>\n ) be the shortest path metric of an edge-weighted graph\n G<\/jats:italic>\n , with the vertex set\n V<\/jats:italic>\n (\n G<\/jats:italic>\n ) and the edge set\n E<\/jats:italic>\n (\n G<\/jats:italic>\n ), on\n n<\/jats:italic>\n vertices. We give the first fixed parameter tractable algorithm that for an\n unweighted<\/jats:italic>\n graph metric\n M<\/jats:italic>\n and integer\n d<\/jats:italic>\n either constructs an embedding of\n M<\/jats:italic>\n into the line with distortion at most\n d<\/jats:italic>\n , or concludes that no such embedding exists. Our algorithm requires\n O<\/jats:italic>\n (\n nd<\/jats:italic>\n 4<\/jats:sup>\n (2\n d<\/jats:italic>\n + 1)\n 2d<\/jats:sup>\n ) time which is a significant improvement over the best previous algorithm that runs in time\n O<\/jats:italic>\n (\n n<\/jats:italic>\n 4d+2<\/jats:sup>\n d<\/jats:italic>\n O(1)<\/jats:sup>\n ). Because of its apparent similarity to the notoriously hard\n Bandwidth Minimization<\/jats:sc>\n problem, we find it surprising that this problem turns out to be fixed parameter tractable.\n <\/jats:p>\n \n We extend our results on embedding unweighted graph metric into the line in two ways. First, we give an algorithm to construct small-distortion embeddings of\n weighted<\/jats:italic>\n graph metrics. The running time of our algorithm is\n O<\/jats:italic>\n (\n n<\/jats:italic>\n (\n dW<\/jats:italic>\n )\n 4<\/jats:sup>\n (2\n d<\/jats:italic>\n + 1)\n 2dW<\/jats:sup>\n ), where\n W<\/jats:italic>\n is the largest edge weight of the input graph. To complement this result, we show that the exponential dependence on the maximum edge weight is unavoidable. In particular, we show that deciding whether a weighted graph metric\n M<\/jats:italic>\n (\n G<\/jats:italic>\n ) with maximum weight\n W<\/jats:italic>\n < |\n V<\/jats:italic>\n (\n G<\/jats:italic>\n )| can be embedded into the line with distortion at most\n d<\/jats:italic>\n is NP-complete for every fixed rational\n d<\/jats:italic>\n \u2265 2. This rules out any possibility of an algorithm with running time\n O<\/jats:italic>\n ((\n nW<\/jats:italic>\n )\n h(d)<\/jats:sup>\n ) where\n h<\/jats:italic>\n is a function of\n d<\/jats:italic>\n alone. Second, we consider more general host metrics for which analogous results hold. In particular, we prove that for any tree\n T<\/jats:italic>\n with maximum degree\n \u0394<\/jats:italic>\n , embedding\n M<\/jats:italic>\n into a shortest path metric of\n T<\/jats:italic>\n is fixed parameter tractable, parameterized by (\n \u0394<\/jats:italic>\n ,\n d<\/jats:italic>\n ).\n <\/jats:p>","DOI":"10.1145\/2489789","type":"journal-article","created":{"date-parts":[[2013,12,10]],"date-time":"2013-12-10T13:28:12Z","timestamp":1386682092000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Distortion is Fixed Parameter Tractable"],"prefix":"10.1145","volume":"5","author":[{"given":"Michael","family":"Fellows","sequence":"first","affiliation":[{"name":"Charles Darwin University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fedor V.","family":"Fomin","sequence":"additional","affiliation":[{"name":"University of Bergen"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[{"name":"University of Bergen"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Elena","family":"Losievskaja","sequence":"additional","affiliation":[{"name":"University of Iceland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frances","family":"Rosamond","sequence":"additional","affiliation":[{"name":"Charles Darwin University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[{"name":"The Institute of Mathematical Sciences"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060624"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201905)","author":"B\u0103doiu Mihai","year":"2005","unstructured":"Mihai B\u0103doiu , Kedar Dhamdhere , Anupam Gupta , Yuri Rabinovich , Harald R\u00e4cke , R. Ravi , and Anastasios Sidiropoulos . 2005 b. 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. Mihai B\u0103doiu, Kedar Dhamdhere, Anupam Gupta, Yuri Rabinovich, Harald R\u00e4cke, R. Ravi, and Anastasios Sidiropoulos. 2005b. 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_3_1","volume-title":"Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201907)","author":"B\u0103doiu Mihai","year":"2007","unstructured":"Mihai B\u0103doiu , Piotr Indyk , and Anastasios Sidiropoulos . 2007 . Approximation algorithms for embedding general metrics into trees . In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201907) . 512--521. Mihai B\u0103doiu, Piotr Indyk, and Anastasios Sidiropoulos. 2007. Approximation algorithms for embedding general metrics into trees. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201907). 512--521."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195229"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00342-9"},{"key":"e_1_2_1_6_1","volume-title":"Fellows","author":"Downey Rodney G.","year":"1999","unstructured":"Rodney G. Downey and Michael R . Fellows . 1999 . Parameterized Complexity. Springer . Rodney G. Downey and Michael R. Fellows. 1999. Parameterized Complexity. Springer."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_39"},{"volume-title":"Parameterized Complexity Theory","author":"Flum J\u00f6rg","key":"e_1_2_1_8_1","unstructured":"J\u00f6rg Flum and Martin Grohe . 2006. Parameterized Complexity Theory . Springer . J\u00f6rg Flum and Martin Grohe. 2006. Parameterized Complexity Theory. Springer."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-004-0015-x"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/11538462_10"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875596"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007398"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the International Congress of Mathematicians.","volume":"3","author":"Linial Nathan","year":"2002","unstructured":"Nathan Linial . 2002 . Finite metric-spaces---Combinatorics, geometry and algorithms . In Proceedings of the International Congress of Mathematicians. Vol. 3 , Higher Education Press, 573--586. Nathan Linial. 2002. Finite metric-spaces---Combinatorics, geometry and algorithms. In Proceedings of the International Congress of Mathematicians. Vol. 3, Higher Education Press, 573--586."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133096"},{"volume-title":"Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and its Applications","author":"Niedermeier Rolf","key":"e_1_2_1_15_1","unstructured":"Rolf Niedermeier . 2006. Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and its Applications , vol. 31 , Oxford University Press . Rolf Niedermeier. 2006. Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and its Applications, vol. 31, Oxford University Press."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/0601042"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2489789","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2489789","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:39:26Z","timestamp":1750235966000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2489789"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,11]]},"references-count":16,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,11]]}},"alternative-id":["10.1145\/2489789"],"URL":"https:\/\/doi.org\/10.1145\/2489789","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2013,11]]},"assertion":[{"value":"2012-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-11-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}