{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,8]],"date-time":"2026-10-08T19:09:10Z","timestamp":1791486550777,"version":"4.3.4"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2022,7,31]],"date-time":"2022-07-31T00:00:00Z","timestamp":1659225600000},"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. Algorithms"],"published-print":{"date-parts":[[2022,7,31]]},"abstract":"<jats:p>\n            We consider the isomorphism problem for hypergraphs taking as input two hypergraphs over the same set of vertices\n            <jats:italic>V<\/jats:italic>\n            and a permutation group \u0393 over domain\n            <jats:italic>V<\/jats:italic>\n            , and asking whether there is a permutation \u03b3 \u03b5 \u0393 that proves the two hypergraphs to be isomorphic. We show that for input groups, all of whose composition factors are isomorphic to a subgroup of the symmetric group on\n            <jats:italic>d<\/jats:italic>\n            points, this problem can be solved in time (\n            <jats:italic>n<\/jats:italic>\n            +\n            <jats:italic>m<\/jats:italic>\n            )\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              ((log\n              <jats:italic>d<\/jats:italic>\n              )\n              <jats:italic>c<\/jats:italic>\n              )\n            <\/jats:sup>\n            for some absolute constant\n            <jats:italic>c<\/jats:italic>\n            where\n            <jats:italic>n<\/jats:italic>\n            denotes the number of vertices and\n            <jats:italic>m<\/jats:italic>\n            the number of hyperedges. In particular, this gives the currently fastest isomorphism test for hypergraphs in general. The previous best algorithm for this problem due to Schweitzer and Wiebking (STOC 2019) runs in time\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (\n              <jats:italic>d<\/jats:italic>\n              )\n            <\/jats:sup>\n            <jats:italic>m<\/jats:italic>\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            .\n          <\/jats:p>\n          <jats:p>\n            As an application of this result, we obtain, for example, an algorithm testing isomorphism of graphs excluding\n            <jats:italic>K<\/jats:italic>\n            <jats:sub>\n              3,\n              <jats:italic>h<\/jats:italic>\n            <\/jats:sub>\n            (\n            <jats:italic>h<\/jats:italic>\n            \u2265 3) as a minor in time\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              ((log\n              <jats:italic>h<\/jats:italic>\n              )\n              <jats:italic>c<\/jats:italic>\n              )\n            <\/jats:sup>\n            . In particular, this gives an isomorphism test for graphs of Euler genus at most\n            <jats:italic>g<\/jats:italic>\n            running in time\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              ((log\n              <jats:italic>g<\/jats:italic>\n              )\n              <jats:italic>c<\/jats:italic>\n              )\n            <\/jats:sup>\n            .\n          <\/jats:p>","DOI":"10.1145\/3527667","type":"journal-article","created":{"date-parts":[[2022,4,21]],"date-time":"2022-04-21T12:47:50Z","timestamp":1650545270000},"page":"1-50","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Hypergraph Isomorphism for Groups with Restricted Composition Factors"],"prefix":"10.1145","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4940-0318","authenticated-orcid":false,"given":"Daniel","family":"Neuen","sequence":"first","affiliation":[{"name":"CISPA Helmholtz Center for Information Security, Saarbr\u00fccken, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,10,11]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"crossref","unstructured":"L\u00e1szl\u00f3 Babai. 2015. Graph isomorphism in quasipolynomial time. arXiv:1512.03547. Retrieved from http:\/\/arxiv.org\/abs\/1512.03547v2.","DOI":"10.1145\/2897518.2897542"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897542"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/0021-8693(82)90323-4"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.25"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.80"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1983.10"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-016-9686-0"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305232"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0731-3"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591865"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1017\/9781009036214.006"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00018"},{"key":"e_1_3_2_14_2","unstructured":"Martin Grohe Daniel Neuen and Pascal Schweitzer. 2018. A faster isomorphism test for graphs of small degree. arXiv:1802.04659v3. Retrieved from http:\/\/arxiv.org\/abs\/1802.04659v3."},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00064"},{"key":"e_1_3_2_16_2","volume-title":"Graph theory","author":"Harary Frank","year":"1991","unstructured":"Frank Harary. 1991. Graph theory. Addison-Wesley."},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(71)90019-6"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_13"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4478-3_5"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_3_2_21_2","unstructured":"Ken-ichi Kawarabayashi. 2015. Graph isomorphism for bounded genus graphs in linear time. arXiv:1511.02460. Retrieved from http:\/\/arxiv.org\/abs\/1511.02460."},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90009-5"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301427"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(79)90043-6"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(83)80048-5"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(83)80047-3"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2016.70"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.18154\/RWTH-2020-00160"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2020.88"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2021.72"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.59"},{"issue":"3","key":"e_1_3_2_32_2","first-page":"552","article-title":"The isomorphism problem for classes of graphs","volume":"304","author":"Ponomarenko Ilia N.","year":"1989","unstructured":"Ilia N. Ponomarenko. 1989. The isomorphism problem for classes of graphs. Doklady Akademii Nauk SSSR 304, 3 (1989), 552\u2013556.","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01098279"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02993245"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4176-8"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316338"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546549"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2020.103"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3527667","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3527667","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:18:53Z","timestamp":1750191533000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3527667"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,31]]},"references-count":37,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,7,31]]}},"alternative-id":["10.1145\/3527667"],"URL":"https:\/\/doi.org\/10.1145\/3527667","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,7,31]]},"assertion":[{"value":"2020-12-11","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-03-18","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-10-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}