{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,17]],"date-time":"2026-03-17T15:51:01Z","timestamp":1773762661923,"version":"3.50.1"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2020,6,6]],"date-time":"2020-06-06T00:00:00Z","timestamp":1591401600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["GR 1492\/14-1"],"award-info":[{"award-number":["GR 1492\/14-1"]}],"id":[{"id":"10.13039\/501100001659","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,7,31]]},"abstract":"<jats:p>\n            We give a new FPT algorithm testing isomorphism of\n            <jats:italic>n<\/jats:italic>\n            -vertex graphs of tree-width\n            <jats:italic>k<\/jats:italic>\n            in time\n            <jats:italic>2<\/jats:italic>\n            <jats:sup>kpolylog(k)<\/jats:sup>\n            <jats:italic>\n              n\n              <jats:sup>3<\/jats:sup>\n            <\/jats:italic>\n            , improving the FPT algorithm due to Lokshtanov, Pilipczuk, Pilipczuk, and Saurabh (FOCS 2014), which runs in time 2\n            <jats:sup>O(k5 log k)<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>5<\/jats:sup>\n            . Based on an improved version of the isomorphism-invariant graph decomposition technique introduced by Lokshtanov et al., we prove restrictions on the structure of the automorphism groups of graphs of tree-width\n            <jats:italic>k<\/jats:italic>\n            . Our algorithm then makes heavy use of the group theoretic techniques introduced by Luks (JCSS 1982) in his isomorphism test for bounded degree graphs and Babai (STOC 2016) in his quasipolynomial isomorphism test. In fact, we even use Babai\u2019s algorithm as a black box in one place.\n          <\/jats:p>\n          <jats:p>\n            We also give a second algorithm that, at the price of a slightly worse running time 2\n            <jats:sup>O(k2 log k)<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>3<\/jats:sup>\n            , avoids the use of Babai\u2019s algorithm and, more importantly, has the additional benefit that it can also be used as a canonization algorithm.\n          <\/jats:p>","DOI":"10.1145\/3382082","type":"journal-article","created":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T00:47:00Z","timestamp":1591490820000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["An Improved Isomorphism Test for Bounded-tree-width Graphs"],"prefix":"10.1145","volume":"16","author":[{"given":"Martin","family":"Grohe","sequence":"first","affiliation":[{"name":"RWTH Aachen University, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Neuen","sequence":"additional","affiliation":[{"name":"RWTH Aachen University, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pascal","family":"Schweitzer","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Kaiserslautern, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Wiebking","sequence":"additional","affiliation":[{"name":"RWTH Aachen University, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,6,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1157970"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897542"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316356"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 24th Symposium on Foundations of Computer Science. IEEE Computer Society, 162--171","author":"Babai L\u00e1szl\u00f3","year":"1983","unstructured":"L\u00e1szl\u00f3 Babai , William M. Kantor , and Eugene M. Luks . 1983. Computational complexity and the classification of finite simple groups . In Proceedings of the 24th Symposium on Foundations of Computer Science. IEEE Computer Society, 162--171 . DOI:https:\/\/doi.org\/10.1109\/SFCS. 1983 .10 10.1109\/SFCS.1983.10 L\u00e1szl\u00f3 Babai, William M. Kantor, and Eugene M. Luks. 1983. Computational complexity and the classification of finite simple groups. In Proceedings of the 24th Symposium on Foundations of Computer Science. IEEE Computer Society, 162--171. DOI:https:\/\/doi.org\/10.1109\/SFCS.1983.10"},{"key":"e_1_2_1_5_1","volume-title":"Luks","author":"Babai L\u00e1szl\u00f3","year":"1983","unstructured":"L\u00e1szl\u00f3 Babai and Eugene M . Luks . 1983 . Canonical labeling of graphs. In Proceedings of the 15th ACM Symposium on Theory of Computing, David S. Johnson, Ronald Fagin, Michael L. Fredman, David Harel, Richard M. Karp, Nancy A. Lynch, Christos H. Papadimitriou, Ronald L. Rivest, Walter L. Ruzzo, and Joel I. Seiferas (Eds.). ACM , 171--183. DOI:https:\/\/doi.org\/10.1145\/800061.808746 10.1145\/800061.808746 L\u00e1szl\u00f3 Babai and Eugene M. Luks. 1983. Canonical labeling of graphs. In Proceedings of the 15th ACM Symposium on Theory of Computing, David S. Johnson, Ronald Fagin, Michael L. Fredman, David Harel, Richard M. Karp, Nancy A. Lynch, Christos H. Papadimitriou, Ronald L. Rivest, Walter L. Ruzzo, and Joel I. Seiferas (Eds.). ACM, 171--183. DOI:https:\/\/doi.org\/10.1145\/800061.808746"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90013-5"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1027320705349"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44867-5_6"},{"key":"e_1_2_1_9_1","volume-title":"Parameterized Algorithms","author":"Cygan Marek","unstructured":"Marek Cygan , Fedor V. Fomin , Lukasz Kowalik , Daniel Lokshtanov , D\u00e1niel Marx , Marcin Pilipczuk , Michal Pilipczuk , and Saket Saurabh . 2015. Parameterized Algorithms . Springer . DOI:https:\/\/doi.org\/10.1007\/978-3-319-21275-3 10.1007\/978-3-319-21275-3 Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, D\u00e1niel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. 2015. Parameterized Algorithms. Springer. DOI:https:\/\/doi.org\/10.1007\/978-3-319-21275-3"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132720"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/120892234"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2019.8785682"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00018"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.66"},{"key":"e_1_2_1_15_1","volume-title":"Isomorphism testing for graphs of bounded rank width. CoRR abs\/1505.03737","author":"Grohe Martin","year":"2015","unstructured":"Martin Grohe and Pascal Schweitzer . 2015. Isomorphism testing for graphs of bounded rank width. CoRR abs\/1505.03737 ( 2015 ). Martin Grohe and Pascal Schweitzer. 2015. Isomorphism testing for graphs of bounded rank width. CoRR abs\/1505.03737 (2015)."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(93)90510-Z"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-99-00288-X"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/140999980"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90009-5"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(79)90004-8"},{"key":"e_1_2_1_21_1","volume-title":"Foundations of Computation Theory","author":"Miller Gary L.","unstructured":"Gary L. Miller . 1983. Isomorphism testing and canonical forms for k-contractable graphs (A generalization of bounded valence and bounded genus) . In Foundations of Computation Theory . Springer Berlin , 310--327. DOI:https:\/\/doi.org\/10.1007\/3-540-12689-9_114 10.1007\/3-540-12689-9_114 Gary L. Miller. 1983. Isomorphism testing and canonical forms for k-contractable graphs (A generalization of bounded valence and bounded genus). In Foundations of Computation Theory. Springer Berlin, 310--327. DOI:https:\/\/doi.org\/10.1007\/3-540-12689-9_114"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 24th European Symposium on Algorithms (ESA\u201916)","volume":"57","author":"Neuen Daniel","year":"2016","unstructured":"Daniel Neuen . 2016 . Graph isomorphism for unit square graphs . In Proceedings of the 24th European Symposium on Algorithms (ESA\u201916) , (LIPIcs), Piotr Sankowski and Christos D. Zaroliagis (Eds.) , Vol. 57 . Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 70:1\u201370:17. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2016.70 10.4230\/LIPIcs.ESA.2016.70 Daniel Neuen. 2016. Graph isomorphism for unit square graphs. In Proceedings of the 24th European Symposium on Algorithms (ESA\u201916), (LIPIcs), Piotr Sankowski and Christos D. Zaroliagis (Eds.), Vol. 57. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 70:1\u201370:17. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2016.70"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-08404-6_32"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01098279"},{"key":"e_1_2_1_25_1","volume-title":"Graph isomorphism in quasipolynomial time parameterized by treewidth. CoRR abs\/1911.11257","author":"Wiebking Daniel","year":"2019","unstructured":"Daniel Wiebking . 2019. Graph isomorphism in quasipolynomial time parameterized by treewidth. CoRR abs\/1911.11257 ( 2019 ). Daniel Wiebking. 2019. Graph isomorphism in quasipolynomial time parameterized by treewidth. CoRR abs\/1911.11257 (2019)."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3382082","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3382082","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:02:08Z","timestamp":1750197728000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3382082"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,6]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,7,31]]}},"alternative-id":["10.1145\/3382082"],"URL":"https:\/\/doi.org\/10.1145\/3382082","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,6,6]]},"assertion":[{"value":"2019-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-06-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}