{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T05:11:28Z","timestamp":1759813888779,"version":"3.41.0"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2021,4,26]],"date-time":"2021-04-26T00:00:00Z","timestamp":1619395200000},"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":["Commun. ACM"],"published-print":{"date-parts":[[2021,5]]},"abstract":"<jats:p>\n            We investigate the interplay between the graph isomorphism problem, logical definability, and structural graph theory on a rich family of dense graph classes: graph classes of bounded rank width. We prove that the combinatorial Weisfeiler-Leman algorithm of dimension (3\n            <jats:italic>k<\/jats:italic>\n            + 4) is a complete isomorphism test for the class of all graphs of rank width at most\n            <jats:italic>k.<\/jats:italic>\n            A consequence of our result is the first polynomial time canonization algorithm for graphs of bounded rank width.\n          <\/jats:p>\n          <jats:p>Our second main result addresses an open problem in descriptive complexity theory: we show that fixed-point logic with counting expresses precisely the polynomial time properties of graphs of bounded rank width.<\/jats:p>","DOI":"10.1145\/3453943","type":"journal-article","created":{"date-parts":[[2021,4,26]],"date-time":"2021-04-26T14:14:22Z","timestamp":1619446462000},"page":"98-105","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Isomorphism, canonization, and definability for graphs of bounded rank width"],"prefix":"10.1145","volume":"64","author":[{"given":"Martin","family":"Grohe","sequence":"first","affiliation":[{"name":"RWTH Aachen University, Aachen, Germany"}]},{"given":"Daniel","family":"Neuen","sequence":"additional","affiliation":[{"name":"RWTH Aachen University, Aachen, Germany"}]}],"member":"320","published-online":{"date-parts":[[2021,4,26]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897542"},{"key":"e_1_2_1_2_1","first-page":"12","article-title":"An optimal lower bound on the number of variables for graph identifications","volume":"4","author":"Cai J.","year":"1992","unstructured":"Cai , J. , F\u00fcrer , M. , Immerman , N . An optimal lower bound on the number of variables for graph identifications . Combinatories 4 , 12 ( 1992 ), 389--410. Cai, J., F\u00fcrer, M., Immerman, N. An optimal lower bound on the number of variables for graph identifications. Combinatories 4, 12 (1992), 389--410.","journal-title":"Combinatories"},{"key":"e_1_2_1_3_1","first-page":"25","article-title":"Structure and complexity of relational queries","volume":"1","author":"Chandra A.K.","year":"1982","unstructured":"Chandra , A.K. , Harel , D . Structure and complexity of relational queries . J. Comput. Syst. Sci. 1 , 25 ( 1982 ), 99--128. Chandra, A.K., Harel, D. Structure and complexity of relational queries. J. Comput. Syst. Sci. 1, 25 (1982), 99--128.","journal-title":"J. Comput. Syst. Sci."},{"key":"e_1_2_1_4_1","first-page":"33","article-title":"Linear time solvable optimization problems on graphs of bounded clique-width","volume":"2","author":"Courcelle B.","year":"2000","unstructured":"Courcelle , B. , Makowsky , J.A. , Rotics , U . Linear time solvable optimization problems on graphs of bounded clique-width . Theory Comput. Syst. 2 , 33 ( 2000 ), 125--150. Courcelle, B., Makowsky, J.A., Rotics, U. Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst. 2, 33 (2000), 125--150.","journal-title":"Theory Comput. Syst."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(99)00184-5"},{"key":"e_1_2_1_6_1","volume-title":"Finite Model Theory","author":"Ebbinghaus H.","year":"1999","unstructured":"Ebbinghaus , H. , Flum , J. Finite Model Theory , 2 nd edn. Springer Verlag , 1999 . Ebbinghaus, H., Flum, J. Finite Model Theory, 2nd edn. Springer Verlag, 1999.","edition":"2"},{"key":"e_1_2_1_7_1","series-title":"Vol. 7","volume-title":"Complexity of Computation, SIAM-AMS Proceedings","author":"Fagin R.","unstructured":"Fagin , R. Generalized first-order spectra and polynomial-time recognizable sets . In Complexity of Computation, SIAM-AMS Proceedings ( Vol. 7 ), R. Karp, ed. (1974), 43--73. Fagin, R. Generalized first-order spectra and polynomial-time recognizable sets. In Complexity of Computation, SIAM-AMS Proceedings (Vol. 7), R. Karp, ed. (1974), 43--73."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1017\/9781139028868"},{"key":"e_1_2_1_9_1","first-page":"44","article-title":"Structure theorem and isomorphism test for graphs with excluded topological subgraphs","volume":"1","author":"Grohe M.","year":"2015","unstructured":"Grohe , M. , Marx , D . Structure theorem and isomorphism test for graphs with excluded topological subgraphs . SIAM J. Comput. 1 , 44 ( 2015 ), 114--159. Grohe, M., Marx, D. Structure theorem and isomorphism test for graphs with excluded topological subgraphs. SIAM J. Comput. 1, 44 (2015), 114--159.","journal-title":"SIAM J. Comput."},{"key":"e_1_2_1_10_1","volume-title":"Canonisation and definability for graphs of bounded rank width. CoRR, abs\/1901.10330","author":"Grohe M.","year":"2019","unstructured":"Grohe , M. , Neuen , D. Canonisation and definability for graphs of bounded rank width. CoRR, abs\/1901.10330 , 2019 . Grohe, M., Neuen, D. Canonisation and definability for graphs of bounded rank width. CoRR, abs\/1901.10330, 2019."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.66"},{"key":"e_1_2_1_12_1","first-page":"30","article-title":"Computing with tangles","volume":"2","author":"Grohe M.","year":"2016","unstructured":"Grohe , M. , Schweitzer , P . Computing with tangles . SIAM J. Discrete Math. 2 , 30 ( 2016 ), 1213--1247. Grohe, M., Schweitzer, P. Computing with tangles. SIAM J. Discrete Math. 2, 30 (2016), 1213--1247.","journal-title":"SIAM J. Discrete Math."},{"key":"e_1_2_1_13_1","volume-title":"Current Trends in Theoretical Computer Science","author":"Gurevich Y.","year":"1988","unstructured":"Gurevich , Y. Logic and the challenge of computer science . In Current Trends in Theoretical Computer Science ( 1988 ), E. B\u00f6rger, ed. Computer Science Press , 1--57. Gurevich, Y. Logic and the challenge of computer science. In Current Trends in Theoretical Computer Science (1988), E. B\u00f6rger, ed. Computer Science Press, 1--57."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/321850.321852"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802187"},{"key":"e_1_2_1_16_1","first-page":"16","article-title":"Languages that capture complexity classes","volume":"4","author":"Immerman N","year":"1987","unstructured":"Immerman , N . Languages that capture complexity classes . SIAM J. Comput. 4 , 16 ( 1987 ), 760--778. Immerman, N. Languages that capture complexity classes. SIAM J. Comput. 4, 16 (1987), 760--778.","journal-title":"SIAM J. Comput."},{"key":"e_1_2_1_17_1","volume-title":"Complexity Theory Retrospective: In Honor of Juris Hartmanis on the Occasion of His Sixtieth Birthday (July 5","author":"Immerman N.","year":"1988","unstructured":"Immerman , N. , Lander , E. Describing graphs: A first-order approach to graph canonization . In Complexity Theory Retrospective: In Honor of Juris Hartmanis on the Occasion of His Sixtieth Birthday (July 5 , 1988 ), A.L. Selman, ed. Springer New York , New York, NY, 1990, 59--81. Immerman, N., Lander, E. Describing graphs: A first-order approach to graph canonization. In Complexity Theory Retrospective: In Honor of Juris Hartmanis on the Occasion of His Sixtieth Birthday (July 5, 1988), A.L. Selman, ed. Springer New York, New York, NY, 1990, 59--81."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.1975.5.1.45"},{"key":"e_1_2_1_19_1","first-page":"25","article-title":"Isomorphism of graphs of bounded valence can be tested in polynomial time","volume":"1","author":"Luks E.M","year":"1982","unstructured":"Luks , E.M . Isomorphism of graphs of bounded valence can be tested in polynomial time . J. Comput. Syst. Sci. 1 , 25 ( 1982 ), 42--65. Luks, E.M. Isomorphism of graphs of bounded valence can be tested in polynomial time. J. Comput. Syst. Sci. 1, 25 (1982), 42--65.","journal-title":"J. Comput. Syst. Sci."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-21676-7"},{"key":"e_1_2_1_21_1","first-page":"96","article-title":"Approximating clique-width and branch-width","volume":"4","author":"Oum S.","year":"2006","unstructured":"Oum , S. , Seymour , P.D . Approximating clique-width and branch-width . J. Comb. Theory, Ser. B 4 , 96 ( 2006 ), 514--528. Oum, S., Seymour, P.D. Approximating clique-width and branch-width. J. Comb. Theory, Ser. B 4, 96 (2006), 514--528.","journal-title":"J. Comb. Theory, Ser. B"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802186"},{"key":"e_1_2_1_23_1","series-title":"NTI Ser. 2","volume-title":"The reduction of a graph to canonical form and the algebra which appears therein","author":"Weisfeiler B.","year":"1968","unstructured":"Weisfeiler , B. , Leman , A. The reduction of a graph to canonical form and the algebra which appears therein . NTI Ser. 2 , 1968 . Available at htttps:\/\/www.iti.zcu.cz\/wl2018\/pdf\/wl_paper_translation.pdf. English transalation by G. Ryabov Weisfeiler, B., Leman, A. The reduction of a graph to canonical form and the algebra which appears therein. NTI Ser. 2, 1968. Available at htttps:\/\/www.iti.zcu.cz\/wl2018\/pdf\/wl_paper_translation.pdf. English transalation by G. Ryabov"}],"container-title":["Communications of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3453943","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3453943","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:47:51Z","timestamp":1750193271000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3453943"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,26]]},"references-count":23,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2021,5]]}},"alternative-id":["10.1145\/3453943"],"URL":"https:\/\/doi.org\/10.1145\/3453943","relation":{},"ISSN":["0001-0782","1557-7317"],"issn-type":[{"type":"print","value":"0001-0782"},{"type":"electronic","value":"1557-7317"}],"subject":[],"published":{"date-parts":[[2021,4,26]]},"assertion":[{"value":"2021-04-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}