{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,3]],"date-time":"2026-10-03T15:36:07Z","timestamp":1791041767698,"version":"4.1.0"},"reference-count":65,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2020,7,6]],"date-time":"2020-07-06T00:00:00Z","timestamp":1593993600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001742","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["592\/17"],"award-info":[{"award-number":["592\/17"]}],"id":[{"id":"10.13039\/501100001742","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2020,10,31]]},"abstract":"<jats:p>\n            The edit distance between two rooted ordered trees with\n            <jats:italic>n<\/jats:italic>\n            nodes labeled from an alphabet \u01a9 is the minimum cost of transforming one tree into the other by a sequence of elementary operations consisting of deleting and relabeling existing nodes, as well as inserting new nodes. Tree edit distance is a well-known generalization of string edit distance. The fastest known algorithm for tree edit distance runs in cubic\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>3<\/jats:sup>\n            ) time and is based on a similar dynamic programming solution as string edit distance. In this article, we show that a truly subcubic\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>3-\u03b5<\/jats:sup>\n            ) time algorithm for tree edit distance is unlikely: For |\u01a9| = \u03a9 (\n            <jats:italic>n<\/jats:italic>\n            ), a truly subcubic algorithm for tree edit distance implies a truly subcubic algorithm for the all pairs shortest paths problem. For |\u01a9| =\n            <jats:italic>O<\/jats:italic>\n            (1), a truly subcubic algorithm for tree edit distance implies an\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>k-\u03b5<\/jats:sup>\n            ) algorithm for finding a maximum weight\n            <jats:italic>k<\/jats:italic>\n            -clique.\n          <\/jats:p>\n          <jats:p>Thus, while in terms of upper bounds string edit distance and tree edit distance are highly related, in terms of lower bounds string edit distance exhibits the hardness of the strong exponential time hypothesis (Backurs, Indyk STOC\u201915) whereas tree edit distance exhibits the hardness of all pairs shortest paths. Our result provides a matching conditional lower bound for one of the last remaining classic dynamic programming problems.<\/jats:p>","DOI":"10.1145\/3381878","type":"journal-article","created":{"date-parts":[[2020,7,6]],"date-time":"2020-07-06T21:17:26Z","timestamp":1594070246000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":32,"title":["Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (Unless APSP Can)"],"prefix":"10.1145","volume":"16","author":[{"given":"Karl","family":"Bringmann","sequence":"first","affiliation":[{"name":"Max Planck Institute for Informatics, Saarland Informatics Campus"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pawe\u0142","family":"Gawrychowski","sequence":"additional","affiliation":[{"name":"University of Wroc\u0142aw"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9262-1821","authenticated-orcid":false,"given":"Shay","family":"Mozes","sequence":"additional","affiliation":[{"name":"IDC Herzliya"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4510-7552","authenticated-orcid":false,"given":"Oren","family":"Weimann","sequence":"additional","affiliation":[{"name":"University of Haifa"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,7,6]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of YR-ICALP Satellite Workshop of ICALP.","author":"Abboud Amir","year":"2014"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch88"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.16"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.14"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Amir Abboud and S\u00f8ren Dahlgaard. 2016. Popular conjectures as a barrier for dynamic planar graph algorithms. In FOCS. 476--486.  Amir Abboud and S\u00f8ren Dahlgaard. 2016. Popular conjectures as a barrier for dynamic planar graph algorithms. In FOCS. 476--486.","DOI":"10.1109\/FOCS.2016.58"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.112"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897653"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39206-1_1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.53"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43948-7_4"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746594"},{"key":"e_1_2_1_12_1","first-page":"90","article-title":"Approximating tree edit distance through string edit distance","volume":"4288","author":"Akutsu Tatsuya","year":"2006","journal-title":"Proceedings of ISAAC"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1388"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings ofIJCAI. 1976--1982","author":"Alur Rajeev","year":"2013"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43948-7_10"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Alberto Apostolico and Zvi Galil (Eds.). 1997. Pattern Matching Algorithms. Oxford University Press Oxford UK.  Alberto Apostolico and Zvi Galil (Eds.). 1997. Pattern Matching Algorithms. Oxford University Press Oxford UK.","DOI":"10.1093\/oso\/9780195113679.001.0001"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/1883466.1883467"},{"key":"e_1_2_1_18_1","first-page":"1","article-title":"Tight hardness results for maximum weight rectangles","volume":"81","author":"Backurs Arturs","year":"2016","journal-title":"Proceedings of ICALP."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746612"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.56"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of ICML. 311--321","author":"Backurs Arturs","year":"2017"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICIAP.1999.797676"},{"key":"e_1_2_1_23_1","volume-title":"Dynamic Programming","author":"Bellman Richard E."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.12.030"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.76"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.69"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.48"},{"key":"e_1_2_1_28_1","volume-title":"A Dichotomy for regular expression membership testing. CoRR abs\/1611.00918","author":"Bringmann Karl","year":"2016"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.15"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-012722442-8\/50021-5"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of VLDB. 90--101","author":"Chawathe Sudarshan S.","year":"1999"},{"key":"e_1_2_1_32_1","unstructured":"Rapha\u00ebl Clifford. 2009. Matrix multiplication and pattern matching under Hamming norm. Retrieved from http:\/\/www.cs.bris.ac.uk\/Research\/Algorithms\/events\/BAD09\/BAD09\/Talks\/BAD09-Hammingnotes.pdf.  Rapha\u00ebl Clifford. 2009. Matrix multiplication and pattern matching under Hamming norm. Retrieved from http:\/\/www.cs.bris.ac.uk\/Research\/Algorithms\/events\/BAD09\/BAD09\/Talks\/BAD09-Hammingnotes.pdf."},{"key":"e_1_2_1_33_1","first-page":"1","article-title":"Fine-grained complexity analysis of two classic TSP variants","volume":"55","author":"de Berg Mark","year":"2016","journal-title":"Proceedings of ICALP"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1644015.1644017"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.05.009"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1613676.1613680"},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","volume-title":"Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology","author":"Gusfield Dan","DOI":"10.1017\/CBO9780511574931"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/322290.322295"},{"key":"e_1_2_1_40_1","volume-title":"Complexity of Computer Computations","author":"Karp Richard M."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-68530-8_8"},{"key":"e_1_2_1_42_1","volume-title":"Proceedings of SODA. 146--155","author":"Klein Philip N.","year":"2005"},{"key":"e_1_2_1_43_1","volume-title":"Kimia","author":"Klein Philip N.","year":"2000"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00264289"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.03.026"},{"key":"e_1_2_1_46_1","first-page":"38","article-title":"Queries and problems","volume":"16","author":"Authors Miscellaneous","year":"1984","journal-title":"SIGACT News"},{"key":"e_1_2_1_47_1","first-page":"415","article-title":"On the complexity of the subgraph problem","volume":"026","author":"Ne\u0161et\u0159il Jaroslav","year":"1985","journal-title":"Commentationes Math. Universitatis Carolinae"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2699485"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8655(02)00382-3"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9401-5"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(77)90064-3"},{"key":"e_1_2_1_52_1","first-page":"309","article-title":"Comparing multiple RNA secondary structures using tree comparisons","volume":"6","author":"Shapiro Bruce A.","year":"1990","journal-title":"Comput. Appl. Biosci."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218082"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90011-3"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/322139.322143"},{"key":"e_1_2_1_56_1","volume-title":"Algorithms on Trees and Graphs","author":"Valiente Gabriel"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/321796.321811"},{"key":"e_1_2_1_58_1","first-page":"14","article-title":"Introduction to Computational Biology: Maps, Sequences and Genomes","volume":"13","author":"Waterman Michael S.","year":"1995","journal-title":"Chapters"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.023"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591811"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.67"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1137\/09076619X"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-28639-4_25"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2007.03.023"},{"key":"e_1_2_1_65_1","volume-title":"Proceedings of HLT-NAACL. 858--867","author":"Yao Xuchen","year":"2013"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1016\/0031-3203(94)00109-Y"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3381878","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3381878","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:33:07Z","timestamp":1750199587000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3381878"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,6]]},"references-count":65,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,10,31]]}},"alternative-id":["10.1145\/3381878"],"URL":"https:\/\/doi.org\/10.1145\/3381878","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,7,6]]},"assertion":[{"value":"2018-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-07-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}