{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,16]],"date-time":"2026-04-16T14:46:23Z","timestamp":1776350783621,"version":"3.51.2"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"2","funder":[{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"crossref","award":["820148"],"award-info":[{"award-number":["820148"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100019180","name":"HORIZON EUROPE European Research Council","doi-asserted-by":"crossref","award":["101054974"],"award-info":[{"award-number":["101054974"]}],"id":[{"id":"10.13039\/100019180","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2026,4,30]]},"abstract":"\n The Weisfeiler-Leman dimension of a graph\n \n \\( G \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is the least number\n \n \\( k \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n such that the\n \n \\( k \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -dimensional Weisfeiler-Leman algorithm distinguishes\n \n \\( G \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n from every other non-isomorphic graph, or equivalently, the least\n \n \\( k \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n such that\n \n \\( G \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is definable in\n \n \\((k+1)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -variable logic with counting. The dimension is a standard measure of the descriptive or structural complexity of a graph and recently finds various applications in particular in the context of machine learning. This article studies the complexity of computing the Weisfeiler-Leman dimension. We observe that deciding whether the Weisfeiler-Leman dimension of\n \n \\( G \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is at most\n \n \\( k \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is\n NP<\/jats:sans-serif>\n -hard, even if\n \n \\( G \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is restricted to have 4-bounded color classes. Therefore, we study parameterized versions of the problem. For each fixed\n \n \\(k\\geq 2\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , we give a polynomial-time algorithm that decides whether the Weisfeiler-Leman dimension of a given graph with 5-bounded color classes is at most\n \n \\( k \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . Moreover, we show that for these bounds on the color classes, this is optimal because the problem is\n P<\/jats:sans-serif>\n -hard under logspace-uniform\n AC<\/jats:sans-serif>\n \n 0<\/jats:sans-serif>\n <\/jats:sub>\n -reductions. Furthermore, for each larger bound\n \n \\( c \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n on the color classes and each fixed\n \n \\(k\\geq 2\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , we provide a polynomial-time decision algorithm for the abelian case, that is, for structures of which each color class has an abelian automorphism group.\n <\/jats:p>\n While the graph classes we consider may seem quite restrictive, graphs with 4-bounded abelian colors include CFI-graphs and multipedes, which form the basis of almost all known hard instances and lower bounds related to the Weisfeiler-Leman algorithm.<\/jats:p>","DOI":"10.1145\/3798282","type":"journal-article","created":{"date-parts":[[2026,3,6]],"date-time":"2026-03-06T14:04:03Z","timestamp":1772805843000},"page":"1-36","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Computational Complexity of the Weisfeiler-Leman Dimension"],"prefix":"10.1145","volume":"27","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5437-8074","authenticated-orcid":false,"given":"Moritz","family":"Lichter","sequence":"first","affiliation":[{"name":"RWTH Aachen University, Aachen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1685-410X","authenticated-orcid":false,"given":"Simon","family":"Ra\u00dfmann","sequence":"additional","affiliation":[{"name":"TU Darmstadt, Darmstadt, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-3585-8213","authenticated-orcid":false,"given":"Pascal","family":"Schweitzer","sequence":"additional","affiliation":[{"name":"TU Darmstadt, Darmstadt, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,4,16]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ESA.2021.6"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/S00037-016-0147-6"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1137\/120867834"},{"key":"e_1_3_2_5_2","volume-title":"Monte-Carlo Algorithms in Graph Isomorphism Testing","author":"Babai L\u00e1szl\u00f3","year":"1979","unstructured":"L\u00e1szl\u00f3 Babai. 1979. Monte-Carlo Algorithms in Graph Isomorphism Testing. Technical Report 79-10. Universit\u00e9 de Montr\u00e9al."},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897542"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1979.8"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793251219"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00228-4"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.IPEC.2023.7"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-0208(08)73545-X"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305232"},{"key":"e_1_3_2_13_2","volume-title":"Lectures on Coherent Configurations","author":"Chen Gang","year":"2019","unstructured":"Gang Chen and Ilia Ponomarenko. 2019. Lectures on Coherent Configurations. Central China Normal University Press. Retrieved from https:\/\/www.pdmi.ras.ru\/\u223cinp\/"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74915-8_10"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1002\/JGT.20461"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1137\/20M1327550"},{"key":"e_1_3_2_17_2","volume-title":"A Subexponential Algorithm for Trivalent Graph Isomorphism","author":"Furst Merrick","year":"1980","unstructured":"Merrick Furst, John Hopcroft, and Eugene M. Luks. 1980. A Subexponential Algorithm for Trivalent Graph Isomorphism. Technical Report. Cornell University."},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/1008354.1008356"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1017\/jsl.2018.33"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/S004939970004"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/2371656.2371662"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00052"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-49257-7_6"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3568025"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1017\/JSL.2015.28"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1006\/INCO.1996.0070"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4478-3_5"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972870.13"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-19754-3_16"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/3333003"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/3417515"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1987.11"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/3572918"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2023.133"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.CSL.2025.13"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1016\/J.JSC.2013.09.003"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1609\/AAAI.V33I01.33014602"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ESA.2017.60"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188900"},{"key":"e_1_3_2_40_2","unstructured":"Thomas Schneider and Pascal Schweitzer. 2024. An upper bound on the Weisfeiler-Leman dimension. arXiv:2403.12581. Retrieved from https:\/\/arxiv.org\/abs\/2403.12581"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0378-3758(98)00064-0"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.MFCS.2024.82"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1006\/JCTB.1993.1027"},{"issue":"9","key":"e_1_3_2_44_2","first-page":"12","article-title":"The reduction of a graph to canonical form and the algebra which appears therein","volume":"2","author":"Weisfeiler B.","year":"1968","unstructured":"B. Weisfeiler and A. Leman. 1968. The reduction of a graph to canonical form and the algebra which appears therein. Nauchn. Tech. Inf. Ser. 2, 9 (1968), 12\u201316. Retrieved from https:\/\/www.iti.zcu.cz\/wl2018\/pdf\/wl_paper_translation.pdf","journal-title":"Nauchn. Tech. Inf. Ser"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44522-8_5"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798282","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,16]],"date-time":"2026-04-16T13:51:29Z","timestamp":1776347489000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798282"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,16]]},"references-count":44,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,4,30]]}},"alternative-id":["10.1145\/3798282"],"URL":"https:\/\/doi.org\/10.1145\/3798282","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"value":"1529-3785","type":"print"},{"value":"1557-945X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,16]]},"assertion":[{"value":"2025-05-21","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-01-27","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-04-16","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}